Pith. sign in

REVIEW 5 minor 25 references

An FPT Algorithm for Diverse Minimum s-t Cuts

T0 review · 0 major / 5 minor · reviewed 2026-07-12 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Finding k minimum s-t cuts that pairwise differ in at least d edges is fixed-parameter tractable in k and d.

desk verdict Clean FPT for the remaining open diversity measure on min s-t cuts; structural reduction plus flow-augmentation, proofs look complete. read the letter →

arxiv 2607.03266 v1 pith:RHHQ3KT7 submitted 2026-07-03 cs.DS

Krishnan Dehaleesan , P{aa}l Gr{o}n{aa}s Drange , Fedor V. Fomin , Petr A. Golovach , Laure Morelle This is my paper · ORCID
classification cs.DS MSC 68Q2705C8590C27
keywords diverseminimumcutss-tfixed-parametertractabilityflowaugmentationcolorcodingparameterizedalgorithmsnetworkflows
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Minimum s-t cuts are fundamental, yet asking for several of them that look different from one another is hard: counting them is #P-complete and even deciding existence of three pairwise-diverse ones is already NP-complete. The paper shows that the decision problem becomes fixed-parameter tractable when both the number of desired cuts k and the minimum pairwise difference d are treated as parameters. After a polynomial preprocessing that either finds a diverse family or reduces every minimum cut to size O((kd)^{2}), the algorithm uses color-coding to isolate candidate edges and flow-augmentation to turn carefully constrained minimal cuts into ordinary minimum cuts that can be found by standard max-flow. The result supplies a constructive FPT algorithm whose running time is (kd)^{O(k^{8} d^{8})} n^{O(1)} and thereby places the “min-diversity” measure of cuts on the same tractable footing that the coverage and sum measures already enjoy.

What carries the argument

A two-stage reduction: first a residual-edge contraction that produces a DAG whose topological orderings generate all minimum cuts, so that any cut larger than (kd)^{2} already yields a diverse family; second, color-coding of active membership regions followed by black-box flow-augmentation that converts inclusion-minimal cuts of bounded size into capacity-minimum cuts that can be recovered by ordinary max-flow on Menger paths.

What would settle it

Exhibit a concrete directed network, integers k and d, and a family of k pairwise d-diverse minimum s-t cuts that the algorithm either fails to find or incorrectly declares nonexistent, or show that some minimal cut of size ≤ (kd)^{2} remains non-minimum after every augmentation set returned by the cited flow-augmentation routine.

Watch

Extended reading notes

Core claim

Diverse Min s-t-Cuts—deciding whether a directed capacitated network contains k minimum-capacity s-t cuts whose pairwise symmetric differences each contain at least d edges (measured by multiplicity)—is fixed-parameter tractable parameterized by k+d, and can be solved constructively in time (kd)^{O(k^{8} d^{8})} n^{O(1)}.

Load-bearing premise

The black-box flow-augmentation procedure correctly turns every inclusion-minimal s-t cut of size at most r into a true minimum cut after adding a modest set of candidate edges; if it misses some of the color-coded cuts that arise, the bounded-size case fails.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper studies Diverse Min s-t-Cuts: decide whether a directed capacitated graph with multiplicities contains k minimum s-t cuts whose pairwise symmetric differences have multiplicity at least d. The problem is #P-hard for d∈{1,2} and NP-complete already for k=3. The main result (Theorem 1.1) is an FPT algorithm running in (kd)^{O(k^8 d^8)} n^{O(1)} time, parameterized by k+d. The algorithm has two phases. Lemma 3.1 preprocesses by contracting residual edges with positive flow and SCCs of the residual graph, producing an equivalent instance whose min-cuts are characterized by topological prefixes of a reversed residual DAG (Lemmas 3.5–3.8); if any min-cut has ≥(kd)^2 edges, k d-diverse cuts are constructed explicitly (Lemma 3.9), otherwise every min-cut has size ≤(kd)^2. Lemma 4.1 then solves the bounded-size case by color-coding active regions and profiles, deterministic flow-augmentation (Kim et al., JACM 2025) to turn inclusion-minimal cuts into capacity-minimum cuts, and Menger-path guessing of colors/multiplicities, followed by ordinary min-cut computations.

Significance. The result fills a natural gap between the polynomial-time solvable cov/sum diversity measures and the #P-hard counting problem, and between the poly-time disjoint-cut case and the NP-hard min-diversity case for fixed k=3. The structural characterization of min-cuts after residual contraction (topological prefixes of the reversed residual DAG) is novel and of independent interest for cut enumeration. The non-trivial combination of color-coding with the recent flow-augmentation black box is a clean algorithmic contribution. The algorithm is constructive and the proofs of the two main lemmas are self-contained once the external flow-augmentation theorem is granted. The running time is superexponential, but the paper correctly notes that existing hardness does not rule out single-exponential dependence; the open questions in §5 are well-chosen.

minor comments (5)
  1. In the running-time claim of Lemma 4.1 the factor is written 2^{k^{2}r}·(dkr)^{O(kr)}·r^{O(r^{4})}·mn log m, while the final simplification after the proof of Lemma 4.1 writes O(2^{O(k^{2}r)}·(dkr)^{O(kr)}·r^{O(r^{4})}·m√n log n). Align the two expressions (the √n vs n discrepancy is harmless but should be consistent).
  2. Lemma 3.9: the argument that |S|≥(kd)^{2} forces at least d(k-1)+1 endpoints on one side is correct for simple graphs, but a one-sentence remark that multiplicities do not create extra endpoints (only extra weight) would make the reduction from the general weighted case fully transparent.
  3. Figure 1 caption and the surrounding text in §3.3 refer to indices v_{j1},…,v_{jk}; the construction in the proof of Lemma 3.9 uses i1,…,ik. Unify the index notation.
  4. In the proof of Lemma 4.3, Step 3, the multiplicity alphabet is written {1,…,d-1,d+}; earlier profiles use [0,d+]. Clarify that zero-multiplicity regions are already excluded by the active-region filter.
  5. A short remark after Theorem 1.1 that the same FPT bound holds for undirected graphs (by the same algorithm, or by the simpler residual contraction mentioned in §5) would be useful for readers primarily interested in the undirected setting.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: self-contained FPT proof via structural preprocessing and black-box flow-augmentation

full rationale

The derivation of Theorem 1.1 is a pure algorithmic existence argument with two independent phases. Lemma 3.1 constructs an equivalent instance (or solves outright) by contracting residual edges of positive flow and SCCs of the residual graph, then invokes the topological-order property of the reversed residual DAG (Lemmas 3.7–3.8) to show that a min-cut of size ≥(kd)² yields k pairwise d-diverse cuts by selecting successive prefixes; all steps are proved from Menger’s theorem, flow conservation and Observation 3.2, without reference to the target FPT claim. Lemma 4.1 then solves the bounded-size case by deterministic color-coding of active regions (Lemma 4.2), a single invocation of the external deterministic flow-augmentation black-box of Kim et al. (Theorem 4.1 / Claim 4.1) that turns inclusion-minimal unit-capacity cuts into capacity-minimum cuts, followed by Menger-path guessing of colors and multiplicities. The flow-augmentation citation is independent (distinct author set, published JACM 2025 result used only as a size-bounded oracle). No parameter is fitted to data, no definition is self-referential, no uniqueness theorem is imported from the present authors, and no known empirical pattern is renamed. The running-time bound follows by direct substitution of the (kd)² size bound into the color-coding and augmentation exponents. The argument is therefore free of the six circularity patterns.

Assumptions & free parameters 0 free parameters · 3 assumptions · 1 invented entities

Standard max-flow/min-cut theory, Menger’s theorem, and the published flow-augmentation black box are the only external pillars. No free parameters are fitted; algorithmic constructs (active regions, profiles, colorings) are defined from the input and do not introduce new physical or mathematical entities.

assumptions (3)
  • standard math Max-flow min-cut theorem and integrality of unit-capacity flows (used throughout for critical edges and Menger paths).
    Invoked as background; Observation 3.1, Lemma 2.2, etc.
  • domain assumption Deterministic flow-augmentation (Kim et al. JACM 2025) produces a set A of size 2^{O(λ^4 log λ)} n^{o(1)} that makes every minimal cut of size ≤λ into a minimum cut.
    Black-box Theorem 4.1; correctness of the whole FPT algorithm rests on it.
  • standard math Existence of (n,s)-perfect hash families of size e^s s^{O(log s)} log n (standard splitter constructions).
    Used for deterministic color-coding in Lemma 4.2.
invented entities (1)
  • Active regions and profiles (R_act, (x_α,r_α))
    purpose: Encode the membership pattern and multiplicity budget of a hypothetical solution family so that color-coding can isolate it.
    Purely algorithmic bookkeeping; no independent existence claim outside the algorithm.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An FPT Algorithm for Diverse Minimum s-t Cuts." pith.science (2026). https://pith.science/paper/RHHQ3KT7

@misc{pith2026260703266,
  author       = {Pith},
  title        = {Pith review of: An FPT Algorithm for Diverse Minimum s-t Cuts},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RHHQ3KT7}},
  note         = {Machine review of arXiv:2607.03266}
}
read the original abstract

We study the problem of finding a family of diverse minimum edge s-t cuts in a directed weighted graph G. Given integers k and d, the task is to decide whether G contains k minimum s-t cuts C_1, ..., C_k such that for any i,j in [k], the number of edges in the symmetric difference of C_i and C_j is at least d. For d being 1 or 2, the problem corresponds to counting minimum s-t cuts in G, which is #P-complete [Provan and Ball, SICOMP 1983]. The problem is also known to be NP-complete already for k = 3 [de Berg, L\'opez Mart\'inez, Spieksma, ISAAC 2024]. Our main result shows that the problem is fixed-parameter tractable (FPT) when parameterized by the combined parameter k + d. The main ingredients of our FPT algorithm build on novel structural properties of diverse minimum s-t cuts and a non-trivial application of the flow-augmentation technique of Kim, Kratsch, Pilipczuk, and Wahlstr\"om [JACM 2025].

Figures

Figures reproduced from arXiv: 2607.03266 by the authors.

Figure 1
Figure 1. Construction of k d-diverse cuts; the cuts (A, B) and (A1, B1), . . .(Ak, Bk) are shown by vertical lines. Note that it may happen that s = vj1 or vjk = vi . of edges in all minimum s–t cuts is bounded. The second step of the algorithm solves the problem when the number of edges in the minimum cut is bounded. Lemmas 3.1 and 4.1 together provide the proof of Theorem 1.1. Indeed, Lemma 3.1 promises to find k d-diverse… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 9 canonical work pages

  1. [1]

    Ahuja, Thomas L

    Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin.Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc., USA, 1993

    1993

  2. [2]

    Color-coding.Journal of the ACM, 42(4):844–856, 1995

    Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding.Journal of the ACM, 42(4):844–856, 1995. doi:10.1145/210332.210337

    doi:10.1145/210332.210337 1995

  3. [3]

    Gutin.Digraphs - Theory, Algorithms and Applications, Second Edition

    Jørgen Bang-Jensen and Gregory Z. Gutin.Digraphs - Theory, Algorithms and Applications, Second Edition. Springer Monographs in Mathematics. Springer, 2009

    2009

  4. [4]

    Fellows, Lars Jaffke, Tom´ aˇ s Masaˇ r´ ık, Mateus de Oliveira Oliveira, Gee- varghese Philip, and Frances A

    Julien Baste, Michael R. Fellows, Lars Jaffke, Tom´ aˇ s Masaˇ r´ ık, Mateus de Oliveira Oliveira, Gee- varghese Philip, and Frances A. Rosamond. Diversity of solutions: An exploration through the lens of fixed-parameter tractability theory.Artificial Intelligence, 303:103644, 2022. doi: 10.1016/j.artint.2021.103644

    doi:10.1016/j.artint.2021.103644 2022

  5. [5]

    Maximum flow and minimum-cost flow in almost-linear time.Journal of the ACM, 72(3):1–103, 2025.doi:10.1145/3728631

    Li Chen, Rasmus Kyng, Yang Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time.Journal of the ACM, 72(3):1–103, 2025.doi:10.1145/3728631

    doi:10.1145/3728631 2025

  6. [6]

    Fomin, Lukasz Kowalik, Daniel Lokshtanov, D´ aniel Marx, Marcin Pilipczuk, Micha l Pilipczuk, and Saket Saurabh.Parameterized Algorithms, volume 4

    Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D´ aniel Marx, Marcin Pilipczuk, Micha l Pilipczuk, and Saket Saurabh.Parameterized Algorithms, volume 4. Springer, 2015. doi: 10.1007/978-3-319-21275-3

    doi:10.1007/978-3-319-21275-3 2015

  7. [7]

    Finding Diverse Minimum s-t Cuts

    Mark de Berg, Andr´ es L´ opez Mart´ ınez, and Frits Spieksma. Finding Diverse Minimum s-t Cuts. LIPIcs, Volume 283, ISAAC 2023, 283:24:1–24:17, 2023.doi:10.4230/LIPICS.ISAAC.2023.24. 13

    doi:10.4230/lipics.isaac.2023.24 2023

  8. [8]

    Disjoint tours and the price of diversity

    Mark de Berg, Andr´ es L´ opez Mart´ ınez, and Frits Spieksma. Disjoint tours and the price of diversity. InWALCOM: Algorithms and Computation, pages 402–417, Singapore, 2026. Springer Nature. doi:10.1007/978-981-95-7127-7_27

    work page doi:10.1007/978-981-95-7127-7_27 2026

Show all 25 references
  1. [9]

    Graduate texts in mathematics, volume 173

    Reinhard Diestel.Graph Theory 5th edition. Graduate texts in mathematics, volume 173. Springer, 2016.doi:10.1007/978-3-662-53622-3

    2016 doi

  2. [10]

    Finding diverse solutions parameterized by cliquewidth

    Karolina Drabik and Tom´ aˇ s Masaˇ r´ ık. Finding diverse solutions parameterized by cliquewidth. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 40, pages 36864–36872, 2026. doi:10.1609/aaai.v40i43.41013

    2026 doi

  3. [11]

    Fomin, Petr A

    Fedor V. Fomin, Petr A. Golovach, Lars Jaffke, Geevarghese Philip, and Danil Sagunov. Diverse pairs of matchings.Algorithmica, 86(6):2026–2040, 2024.doi:10.1007/s00453-024-01214-7

    2026 doi

  4. [12]

    Fomin, Petr A

    Fedor V. Fomin, Petr A. Golovach, Fahad Panolan, Geevarghese Philip, and Saket Saurabh. Diverse collections in matroids and graphs.Mathematical Programming, 204(1):415–447, 2024. doi:10. 1007/s10107-023-01959-z

    2024

  5. [13]

    Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, and Yota Otachi. A framework to design approximation algorithms for finding diverse solutions in combinatorial problems.Proceedings of the AAAI Conference on Artificial Intelligence, 37(4):396...

    2023 doi

  6. [14]

    Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, See Woo Lee, and Yota Otachi. Computing diverse shortest paths efficiently: A theoretical and experimental study.Proceedings of the AAAI Conference on Artificial Intelligence, 36(4):3758–3766, 2022.doi:10.1609/aaai.v36i4.20290

    2022 doi

  7. [15]

    Finding diverse trees, paths, and more.Proceedings of the AAAI Conference on Artificial Intelligence, 35(5):3778–3786, 2021

    Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, and Yota Otachi. Finding diverse trees, paths, and more.Proceedings of the AAAI Conference on Artificial Intelligence, 35(5):3778–3786, 2021. doi:10.1609/aaai.v35i5.16495

    2021 doi

  8. [16]

    Karger and Clifford Stein

    David R. Karger and Clifford Stein. A new approach to the minimum cut problem.Journal of the ACM, 43(4):601–640, 1996.doi:10.1145/234533.234534

    1996 doi

  9. [17]

    Flow-augmentation I: Directed graphs.Journal of the ACM, 72(1):1–38, 2025.doi:10.1145/3706103

    Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlstr¨ om. Flow-augmentation I: Directed graphs.Journal of the ACM, 72(1):1–38, 2025.doi:10.1145/3706103

    2025 doi

  10. [18]

    Pearson, 2006

    Jon Kleinberg and ´Eva Tardos.Algorithm design. Pearson, 2006

    2006

  11. [19]

    Ching-Chung Kuo, Fred Glover, and Krishna S. Dhir. Analyzing and modeling the maximum diversity problem by zero-one programming.Decision Sciences, 24(6):1171–1185, 1993. doi: 10.1111/j.1540-5915.1993.tb00509.x

    1993 doi

  12. [20]

    On the structure of all minimum cuts in a network and applications

    Jean-Claude Picard and Maurice Queyranne. On the structure of all minimum cuts in a network and applications. InCombinatorial Optimization II, pages 8–16. Springer Berlin Heidelberg, Berlin, Heidelberg, 1980.doi:10.1007/BFb0120902

    1980 doi

  13. [21]

    Scott Provan and Michael O

    J. Scott Provan and Michael O. Ball. The complexity of counting cuts and of computing the probability that a graph is connected.SIAM Journal on Computing, 12(4):777–788, 1983. doi:10.1137/0212053

    1983 doi

  14. [22]

    Scott Provan and Douglas R

    J. Scott Provan and Douglas R. Shier. A paradigm for listing (s, t)-cuts in graphs.Algorithmica, 15(4):351–372, 1996.doi:10.1007/BF01961544

    1996 doi

  15. [23]

    Depth-first search and linear graph algorithms.SIAM Journal on Computing, 1(2):146–160, 1972.doi:10.1137/0201010

    Robert Tarjan. Depth-first search and linear graph algorithms.SIAM Journal on Computing, 1(2):146–160, 1972.doi:10.1137/0201010

    1972 doi

  16. [24]

    Tsukiyama, I

    S. Tsukiyama, I. Shirakawa, H. Ozaki, and H. Ariyoshi. An algorithm to enumerate all cutsets of a graph in linear time per cutset.J. ACM, 27(4):619–632, 1980.doi:10.1145/322217.322220

    1980 doi

  17. [25]

    Donald K. Wagner. Disjoint ( s, t)-cuts in a network.Networks, 20(4):361–371, 1990. doi:10.1002/ net.3230200402. 14

    1990

Pith tools

Reviewed July 12, 2026 · model on record in the stance chip above.