{"id":"25ac037b-cc46-4d9c-b23c-0558e41ca8aa","arxiv_id":"2411.15282","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For fixed Δ and fixed k, every integer program on a totally Δ-modular matrix with at most two non-zero entries per row outside k extra rows and columns can be solved in strongly polynomial time.","lead":"The paper presents a strongly polynomial-time algorithm for integer programs whose constraint matrices have bounded subdeterminants and at most two non-zero entries per row after deleting a constant number of rows and columns. It extends a 2025 result of Fiorini, Joret, Weltge and Yuditsky to settings with a few extra budget or exactness constraints.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Strong polynomiality of Theorem 4 is unsupported: its proof invokes Theorem 1 only as polynomial-time, and no argument shows the DP's type-(ii) local solver is strongly polynomial.","rationale":"The paper's structural content is substantial and appears sound: Proposition 11 correctly relates alternating tree weight to subdeterminants, Lemma 12 and Theorem 16 provide a decomposition that avoids the surface-embedding case, and the DP is a plausible composition. The reader's concern is exactly the right one: polynomial-time black boxes do not compose into strongly polynomial algorithms. The type-(ii) local instances are full IPs with two nonzeros per row and no extra rows after fixing terminals, so their solver is decisive. If Theorem 1 is not strongly polynomial, Theorem 4 as stated is not established; the result would still be a polynomial-time algorithm. The same issue affects the LP solve used for recentering in Proposition 8, so fixing only the type-(ii) solver may not suffice. I therefore keep the conditional verdict: accept only after the complexity of the black boxes is verified or the theorem is downgraded to polynomial time.","tokens_in":14130,"tokens_out":11102,"duration_ms":120277,"concrete_test":"Extract the explicit running-time bound from the proof of Theorem 1 in Fiorini, Joret, Weltge and Yuditsky (J. ACM 2025), and check whether it is polynomial in m,n with no dependence on the bit lengths of the input entries. If the bound contains factors such as log ||b|| or log ||c||, substitute it into the DP analysis of Theorem 4 and verify that the number of arithmetic operations is not strongly polynomial; that would confirm the concern. Also check whether the LP relaxation step in Proposition 8 can be solved by a strongly polynomial algorithm for the stated matrix class; if not, the same gap appears earlier.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 4 (Section 6, last paragraph) says that each local instance can be solved in polynomial time, and for bags of type (ii) this means invoking Theorem 1. But the paper states Theorem 1 only as a polynomial-time algorithm, and strongly polynomial time is not implied by polynomial time. The DP has polynomially many bags and polynomially many states per bag, so the overall conclusion of strong polynomiality requires every local call to run in strongly polynomial time. No analysis is given of the running time of the Fiorini-Joret-Weltge-Yuditsky algorithm, e.g. whether it depends on log ||b||, log ||c||, or uses an integer-programming oracle; if it does, the final bound is only weakly polynomial. A second black-box transfer occurs in Proposition 8: the reduction recenters around an optimal solution x* of the LP relaxation, but no strongly polynomial LP solver is identified for the class with extra rows W. The central claim therefore rests on unstated complexity strengthenings.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies integer programs of the form min{c^T x : M x ≤ b, x ∈ Z^n} for totally Δ-modular matrices M that have at most two non-zeros per row after deleting at most k rows and columns, for fixed Δ and k (Problem 2). The main theorem, Theorem 4, claims a strongly polynomial-time algorithm for this class. The proof reduces Problem 2 to Problem 3, where a {0, ±1} matrix A with two non-zeros per row is augmented by k arbitrary rows W. The paper represents A via a signed graph, introduces the alternating weight of a tree, shows that bounded subdeterminants imply the absence of large decorated trees, applies a tree-decomposition theorem of Ding, and then uses a bottom-up dynamic program over the decomposition. Corollaries give an FPT algorithm for Problem 3 when A is totally unimodular and an FPT algorithm for the k-dimensional partially ordered knapsack problem.","tokens_in":14280,"tokens_out":15835,"duration_ms":163432,"significance":"If the main claim is correct, this is a meaningful extension of the tractability boundary for IPs with bounded subdeterminants, going beyond the two-nonzeros-per-row case of Fiorini et al. and the cographic nearly-totally-unimodular case of Aprile et al. The structural analysis is largely self-contained: the alternating-weight bound in Proposition 11, the decorated-tree obstruction in Lemma 12, and the tree-decomposition in Theorem 16 are clear and seem correct. The dynamic program is also reasonably explicit. However, the advertised strongly polynomial complexity is not supported by the written proof. Theorem 1, the main black box, is stated only as polynomial-time, and the reduction in Proposition 8 uses an LP relaxation solution without a strong-polynomiality argument. As written, the proof supports at most a polynomial-time algorithm under the stated black boxes. This gap affects the central claim of the paper.","major_comments":[{"comment":"The proof states that each local instance can be solved in polynomial time and that for bags of type (ii) this is done by invoking Theorem 1, which the manuscript states as a polynomial-time algorithm. Polynomial time does not imply strongly polynomial time; if the Fiorini-Joret-Weltge-Yuditsky algorithm depends on log ||b||, log ||c||, or uses an integer-programming oracle, the overall DP is only weakly polynomial. Since Theorem 4 explicitly claims a strongly polynomial-time algorithm, the proof must either give a strongly polynomial version of the type-(ii) solver or the theorem must be weakened to polynomial time. This is the central load-bearing step of the paper.","section":"Section 6, proof of Theorem 4, runtime paragraph"},{"comment":"The reduction from Problem 2 to Problem 3 uses an optimal solution x* of the LP relaxation to recenter the variables and then solves a polynomial number of Problem 3 instances. No strongly polynomial algorithm is identified for solving that LP relaxation for the class in Problem 2, and the extra rows W may have many non-zeros per row. Moreover, Proposition 8 is itself stated only as a polynomial-time reduction. Therefore, even a strongly polynomial algorithm for Problem 3 would not automatically imply Theorem 4 without an additional argument. The proof of Theorem 4 says 'by Proposition 8 it suffices to give a polynomial-time algorithm for Problem 3,' which confirms that the written argument establishes at most polynomial time, not strong polynomiality.","section":"Section 3, Proposition 8 and its proof"}],"minor_comments":[{"comment":"The state-count expression '(2n∆f7(n,∆)+1)^k · (2f7(n,∆)+1)^{O((k∆)^2)}' is polynomial in n for fixed ∆ and k, but the paper should say this explicitly and state the arithmetic model, since the distinction between polynomial and strongly polynomial time is central to the main theorem.","section":"Section 6"},{"comment":"The treatment of disconnected graphs is quite compressed: the reader must infer how the bags of the component decompositions are combined with the empty bags at the c_i nodes. A short explicit construction of the bags for the comb attachments would improve readability.","section":"Section 5, proof of Theorem 16"},{"comment":"Reference [12] contains a corrupted author name ('W˛egrzycki'), and the paper uses both 'parametrized' and 'parameterized'; these should be normalized.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"I would ask the author to resolve the mismatch between Theorem 1 (polynomial-time) and Theorem 4 (strongly polynomial) before further review. If the Fiorini-Joret-Weltge-Yuditsky result is actually strongly polynomial, a short explicit statement in Theorem 1 will fix the issue; otherwise the abstract and main theorem should be revised to polynomial-time, and the significance should be repositioned accordingly. The structural results and the DP would still be a substantive contribution in the latter case."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper has a real new theorem—extending the Fiorini–Joret–Weltge–Yuditsky two-nonzeros-per-row algorithm to allow a constant number of extra rows and columns—and the signed-graph machinery it introduces is worth reading. The structural results in Sections 4 and 5 are clean, especially the alternating-weight invariant in Proposition 11 and the decorated-tree bound in Lemma 12. Avoiding the graph minor structure theorem is a genuine plus; Theorem 16's decomposition is built from elementary tools and appears correct. I also see no circular reasoning: the subdeterminant bounds are assumptions, not conclusions, and the citation to the author's thesis for Corollary 5 is fine.\n\nThe soft spot is the strong-polynomiality claim. The proof of Theorem 4 solves type-(ii) bags by invoking Theorem 1 as a black box after fixing terminal variables. But Theorem 1 is stated only as polynomial-time. Strong polynomiality of the whole DP requires that the local solver for bounded subdeterminants and two nonzeros per row runs in time polynomial in n (with Δ fixed) and independent of the bit lengths of b and c. No argument in the paper establishes that; it may be true, but it is not shown. The reduction in Proposition 8 also recenters around an LP relaxation, and again no strongly polynomial LP solver is identified for the matrix class with extra rows. So the main theorem, as written, is not fully supported. If the claim were weakened to polynomial-time, the paper would be on solid ground and the contribution would still be new. Also, the DP correctness proof is terse—the induction in Section 6 is more of a sketch than a full argument, and the 'all optimal solutions decompose' step deserves a careful proof.\n\nNone of this is a takedown. The structural core is sound and the techniques should be useful. A serious referee could resolve the complexity gap by either strengthening Theorem 1 (or its known running time) or adjusting the theorem statement. The paper deserves peer review; I would not desk-reject it. It is aimed at the bounded-subdeterminant IP community and researchers working on FPT for knapsack-like problems. I'd bring it to a seminar and cite the alternating-weight lemma.","headline":"Real extension of the two-nonzeros-per-row IP result with a nice signed-graph decomposition, but the strong-polynomiality claim rests on an unproven black-box transfer.","tokens_in":14829,"tokens_out":4950,"would_cite":true,"duration_ms":47233,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C10","90C27","05C85","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"For fixed Δ and k, this paper provides a strongly polynomial-time algorithm for integer programs whose totally Δ-modular constraint matrix has at most two non-zeros per row after deleting at most k rows and columns.","keywords":["integer programming","totally Δ-modular matrices","bounded subdeterminants","two non-zeros per row","tree-decomposition","dynamic programming","partially ordered knapsack","parameterized complexity"],"falsifier":"A direct test: find a fixed-Δ, two-nonzero-per-row IP whose only algorithms require a number of arithmetic operations that grows with the bit length of the entries; because such IPs are exactly the type-(ii) leaf subproblems, the dynamic program could not be strongly polynomial unless that base case is. Concretely, checking whether Theorem 1 can be strengthened to strongly polynomial, or finding a lower bound showing it cannot, would settle Theorem 4 as stated.","tokens_in":13890,"feed_emoji":"🧮","tokens_out":8697,"duration_ms":78533,"temperature":0.7,"pith_summary":"Integer programs with bounded subdeterminants are conjectured to be solvable in polynomial time, and this paper proves a new case of that conjecture. Fix Δ and k; if the constraint matrix is totally Δ-modular (every subdeterminant has absolute value at most Δ) and has at most two non-zeros per row after deleting at most k rows and columns, then the IP can be solved in strongly polynomial time. The result extends the known polynomial-time treatment of the two-nonzero case by allowing additional unifying constraints and variables. The proof reduces the general instance to a central problem with k extra rows, translates the subdeterminant bound into a graph-theoretic decomposition, and solves the pieces with a dynamic program. Two fixed-parameter-tractable corollaries follow, including an FPT algorithm for the k-dimensional partially ordered knapsack problem.","feed_headline":"Two-nonzero IPs with k extra rows solve in strongly polynomial time","feed_subtitle":"For fixed Δ and k, totally Δ-modular IPs with at most two nonzeros per row outside k rows and columns become tractable.","key_machinery":"The central object is the alternating weight of a tree: for a signed graph S with vertex weights w, a tree T has bipartition X_T,Y_T such that even edges stay inside a part and odd edges cross, and alt(T,w) = |Σ_{v∈X_T}w(v) − Σ_{v∈Y_T}w(v)|; alt(S,w) is the maximum over all trees. Proposition 11 shows that this quantity is always a subdeterminant of [A; w^T], hence bounded by Δ. Lemma 12 then shows that a graph containing an r-decorated tree — a tree with at least r terminal leaves — forces some weight function to have alternating weight at least r/(2k), so bounded subdeterminants forbid such trees. That absence is exactly what a graph-decomposition lemma (Theorem 13) needs to hand the paper a star-decomposition with a bounded number of terminals at the center, which the paper refines into the type-(i)/(ii) tree-decomposition of Theorem 16 that the dynamic program runs on.","core_discovery":"The paper's central claim is Theorem 4: for fixed constants Δ and k, every instance of Problem 2 — an integer program whose totally Δ-modular matrix has at most two non-zeros per row after removing at most k rows and columns — is solvable in strongly polynomial time. The argument works by a polynomial reduction to Problem 3, where the only messy part is a matrix with two non-zeros per row plus k extra rows; there, the bound on subdeterminants is shown to imply a structural restriction on an associated signed graph. Proposition 11 identifies the alternating weight of a tree as a subdeterminant, Lemma 12 turns bounded alternating weight into the absence of large decorated trees, and Theorem 16 converts that absence into a tree-decomposition with bounded adhesion and degree in which every leaf bag's terminals reappear in its parent. A bottom-up dynamic program on this decomposition solves the instance, with leaf bags handled either by bounded enumeration or by the black-box two-nonzero base case of Theorem 1.","pith_inferences":["If the base case of Theorem 1 is only weakly polynomial, the paper's main theorem still holds as a polynomial-time statement but not as a strongly polynomial one; the gap is local, not in the decomposition.","The alternating-weight invariant could serve as a certificate for bounded subdeterminants in other matrix families: any graph with a tree whose alternating weight exceeds a known bound cannot be the signed graph of a totally Δ-modular matrix.","The sharp contrast with the cographic near-totally-unimodular setting — where almost-embeddable bags are necessary — suggests testing whether allowing both almost-embeddable bags and two-nonzero structure yields a still larger tractable class.","A concrete computational test: generate random totally Δ-modular instances with fixed Δ,k and growing coefficient sizes; if the observed runtime grows with bit length, suspect the missing strongly-polynomial base case."],"forward_implications":["For fixed Δ and k, the algorithmic boundary of bounded-subdeterminant IPs now includes all matrices that become two-nonzero per row after deleting at most k rows and columns.","The reduction to Problem 3 means the proximity theorem of Cook et al. is used directly, avoiding auxiliary proximity or solution-decomposition results needed elsewhere.","When the matrix is totally unimodular, Corollary 5 gives an FPT algorithm for Problem 3 parameterized by the largest subdeterminant, using a dimension-free proximity bound.","Corollary 6 gives an FPT algorithm for the k-dimensional partially ordered knapsack problem, parameterized by the maximum total weight of a connected subgraph, a case for which few polynomial results were known.","The structural decomposition theorem (Theorem 16) shows that the hard almost-embeddable bags of the cographic case are never needed for two-nonzero-plus-k matrices."],"supporting_citations":[{"why":"Supplies Theorem 1, the polynomial-time base-case algorithm for totally Δ-modular IPs with two non-zeros per row, invoked as a black box for type-(ii) bags.","marker":"[16]"},{"why":"Provides the proximity theorem (Theorem 7) used to guess a constant number of variables and recenter the instance in the reduction from Problem 2 to Problem 3.","marker":"[7]"},{"why":"Provides the template for the bottom-up dynamic program and, in Corollary 5, the dimension-free proximity result used to make the FPT statement parameterized by the subdeterminant.","marker":"[2]"},{"why":"Provides the graph decomposition lemma (Theorem 13) that yields the star-decomposition with bounded terminals at the center, refined in Theorem 16.","marker":"[11]"},{"why":"Gives Proposition 9, relating subdeterminants of a signed-graph incidence matrix to the odd-cycle packing number, which anchors the alternating-weight connection.","marker":"[18]"},{"why":"Supplies the strongly polynomial algorithm for combinatorial linear programs, used to solve local problems when the matrix is totally unimodular (Corollary 5).","marker":"[28]"}],"fun_headline_variants":["Strongly poly time for Δ-modular IPs with few extra rows","Two-nonzero rows plus k extra: IPs solved in poly time","Bounded subdeterminant IPs with extra rows now in P","IPs with mostly two nonzeros per row are poly-time solvable","Totally Δ-modular IPs with two nonzeros per row: poly time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The claim of strong polynomiality is supported only if the black-box algorithm for the two-nonzero base case (Theorem 1) is itself strongly polynomial for fixed Δ, yet the paper states that theorem as merely polynomial-time.","fun_headline_variants_meta":{"raw":{"variants":["Strongly poly time for Δ-modular IPs with few extra rows","Two-nonzero rows plus k extra: IPs solved in poly time","Bounded subdeterminant IPs with extra rows now in P","IPs with mostly two nonzeros per row are poly-time solvable","Totally Δ-modular IPs with two nonzeros per row: poly time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000993,"raw_usage":{"total_tokens":4160,"prompt_tokens":850,"completion_tokens":3310,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":466,"completion_tokens_details":{"reasoning_tokens":3211}},"tokens_in":466,"tokens_out":3310,"duration_ms":25265,"temperature":1.0,"reasoning_tokens":3211,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:35:13.089155+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A direct test: find a fixed-Δ, two-nonzero-per-row IP whose only algorithms require a number of arithmetic operations that grows with the bit length of the entries; because such IPs are exactly the type-(ii) leaf subproblems, the dynamic program could not be strongly polynomial unless that base case is. Concretely, checking whether Theorem 1 can be strengthened to strongly polynomial, or finding a lower bound showing it cannot, would settle Theorem 4 as stated.","supporting_citations":[{"cited_title":"Journal of the ACM72(1), 1–50 (2025)","cited_arxiv_id":null,"evidence_quote":"Supplies Theorem 1, the polynomial-time base-case algorithm for totally Δ-modular IPs with two non-zeros per row, invoked as a black box for type-(ii) bags."},{"cited_title":"Mathematical Programming 34(3), 251–264 (1986)","cited_arxiv_id":null,"evidence_quote":"Provides the proximity theorem (Theorem 7) used to guess a constant number of variables and recenter the instance in the reduction from Problem 2 to Problem 3."},{"cited_title":"ACM-SIAM Sym- posium on Discrete Algorithms (SODA25) (2025)","cited_arxiv_id":null,"evidence_quote":"Provides the template for the bottom-up dynamic program and, in Corollary 5, the dimension-free proximity result used to make the FPT statement parameterized by the subdeterminant."},{"cited_title":"Graphs without large $K_{2,n}$-minors","cited_arxiv_id":"1702.01355","evidence_quote":"Provides the graph decomposition lemma (Theorem 13) that yields the star-decomposition with bounded terminals at the center, refined in Theorem 16."},{"cited_title":"Linear Algebra and its Applications 218, 213–224 (1995)","cited_arxiv_id":null,"evidence_quote":"Gives Proposition 9, relating subdeterminants of a signed-graph incidence matrix to the odd-cycle packing number, which anchors the alternating-weight connection."},{"cited_title":"Op- erations Research 34(2), 250–256 (1986)","cited_arxiv_id":null,"evidence_quote":"Supplies the strongly polynomial algorithm for combinatorial linear programs, used to solve local problems when the matrix is totally unimodular (Corollary 5)."}],"review_version":1}