{"id":"4fd37759-48a8-4ad6-8604-3266d935ab7b","arxiv_id":"2607.03266","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.5,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Diverse Min s-t-Cuts is FPT parameterized by k+d, via structural reduction of large cuts plus color-coding and flow-augmentation.","lead":"The paper gives a fixed-parameter algorithm that finds k minimum s-t cuts that are pairwise diverse by at least d edges, running in time depending only on k and d (plus polynomial in the graph size). This settles the parameterized complexity of the min-diversity measure for cuts, which was already NP-hard for three cuts.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly isolates the heaviest external dependency (flow-augmentation) yet notes that it is an accepted, properly cited technique whose failure modes do not appear inside the paper’s own reductions. My re-examination of the two phases finds the same: the novel structural properties (critical/residual partition, residual-DAG acyclicity, and the “every prefix is a min-cut” property) are proved in detail and suffice for the (kd)^{2} bound; the subsequent color-coding, profile enumeration, and path-type guessing are standard FPT bookkeeping whose correctness follows once augmentation is granted. Because no load-bearing gap materializes, the ACCEPT verdict and high-confidence assessment stand unchanged.","tokens_in":18398,"tokens_out":465,"duration_ms":5171,"concrete_test":"Independently re-derive the topological-order claim of Lemma 3.8 from the residual-DAG construction of Lemmas 3.7 and 3.4 without invoking Observation 3.2; if every prefix cut remains capacity-minimum, the large-cut reduction of Lemma 3.9 is confirmed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 1.1) rests on two self-contained phases whose proofs appear complete: (1) the structural preprocessing of §3 that either produces k d-diverse min-cuts or reduces every min-cut to size ≤(kd)^{2} (Lemmas 3.1–3.9, using residual-edge contractions, SCCs, and the topological-order property of the reversed residual DAG), and (2) the color-coding + flow-augmentation + Menger-path guessing of §4 that solves the bounded-size case (Lemmas 4.1–4.4). The only external black-box is the deterministic flow-augmentation of Kim et al. (Theorem 4.1 / Claim 4.1). That result is correctly cited, its size bounds are used faithfully, and the reduction from capacity-min cuts to inclusion-minimal unit-capacity cuts is standard. No internal inconsistency, missing case, or unjustified leap is visible in the supplied arguments.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","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.","tokens_in":18614,"tokens_out":1005,"duration_ms":8707,"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.","major_comments":[],"minor_comments":[{"comment":"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).","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is ready for acceptance. The only external dependency is the deterministic flow-augmentation result of Kim et al. (JACM 2025), which is correctly cited and whose size bounds are used faithfully; no independent verification of that black box is required for this paper. The contribution is solid algorithmic theory and fits a standard algorithms journal."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper settles the last open diversity measure for min s-t cuts: min pairwise symmetric difference. de Berg et al. already had poly-time for cov and sum, and NP-hardness for min even at k=3; here they show FPT in k+d with a constructive algorithm that either returns the cuts or correctly says no.\n\nWhat is new is the structural preprocessing. After contracting residual edges with flow and residual SCCs, the reversed residual graph is a DAG, and every min-cut becomes a prefix of a topological order (Lemma 3.8). That immediately gives the large-cut case: if any min-cut has ≥(kd)^{2} edges you can greedily pick k d-diverse ones from the prefixes. The equivalence of the contracted instance is carefully proved (3.5–3.6). The bounded case is then standard color-coding of the 2^k membership vectors, flow-augmentation to turn the desired minimal cuts into capacity-min cuts, and Menger-path guessing of colors/multiplicities. All of that is written out with explicit bounds.\n\nSoft spots are real but proportional. The runtime is (kd)^{O(k^8 d^8)} n^{O(1)}, which is FPT but tower-like; they flag this themselves and ask for single-exp. Everything rides on the Kim et al. flow-augmentation black box; if that fails for some of the color-coded minimal cuts the reduction collapses, but the citation and size bounds are used faithfully and the reduction from capacity-min to unit-capacity minimal is standard. No circularity, no missing cases I can see, citations are appropriate.\n\nThis is for people who work on cut/flow FPT or diversity in combinatorial optimization. The math is solid enough that a serious editor should send it to referees; I would bring it to reading group and expect to cite the structural lemmas if I ever need diverse cuts.","headline":"Clean FPT for the remaining open diversity measure on min s-t cuts; structural reduction plus flow-augmentation, proofs look complete.","tokens_in":19263,"tokens_out":487,"would_cite":true,"duration_ms":5243,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q27","05C85","90C27"],"pacs":[],"model":"grok-4.5","headline":"Finding k minimum s-t cuts that pairwise differ in at least d edges is fixed-parameter tractable in k and d.","keywords":["diverse minimum cuts","s-t cuts","fixed-parameter tractability","flow augmentation","color coding","parameterized algorithms","network flows"],"falsifier":"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.","tokens_in":19315,"feed_emoji":"✂️","tokens_out":712,"duration_ms":6295,"temperature":0.7,"pith_summary":"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.","feed_headline":"Diverse min-cuts become FPT in k and d","feed_subtitle":"An algorithm finds k pairwise d-different minimum s-t cuts or correctly reports none exist","key_machinery":"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.","core_discovery":"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)}.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Diverse min s-t cuts turn FPT under k+d","FPT algorithm decides k diverse min s-t cuts by k+d","k min s-t cuts with pairwise d-diff are FPT","Diverse min-cuts FPT via flow-augmentation and structure","Finding k d-diverse min s-t cuts is FPT in k+d"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Diverse min s-t cuts turn FPT under k+d","FPT algorithm decides k diverse min s-t cuts by k+d","k min s-t cuts with pairwise d-diff are FPT","Diverse min-cuts FPT via flow-augmentation and structure","Finding k d-diverse min s-t cuts is FPT in k+d"]},"model":"grok-4.5","effort":"low","cost_usd":0.00452,"raw_usage":{"total_tokens":1300,"prompt_tokens":772,"num_sources_used":0,"completion_tokens":99,"cost_in_usd_ticks":45200000,"prompt_tokens_details":{"text_tokens":772,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":429,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":772,"tokens_out":99,"duration_ms":4424,"temperature":1.0,"reasoning_tokens":429,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-12T03:39:39.662458+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"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.","supporting_citations":[],"review_version":1}