A Faster Deterministic Algorithm for Mader's $\mathcal{S}$-Path Packing

Hirota Kinoshita; Satoru Iwata

REVIEW 2 major objections 4 minor 46 references

A Faster Deterministic Algorithm for Mader's $\mathcal{S}$-Path Packing

T0 review · 2 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read A deterministic O(mnk) algorithm solves Mader's S-path packing, removing matrix multiplication from the bottleneck.

desk verdict A genuinely new combinatorial subroutine for dependence-matrix updates yields an O(mnk) deterministic algorithm for Mader's S-path packing, but two load-bearing gaps need proof. read the letter →

arxiv 2411.18292 v1 pith:VNT6H7MI submitted 2024-11-27 cs.DS cs.DMmath.CO

Satoru Iwata , Hirota Kinoshita This is my paper · ORCID

classification cs.DScs.DMmath.CO MSC 05C8505B3568Q2568W40

keywords Mader'sS-pathpackinglinearmatroidparitydependencematrixaugmentingpathalgorithmdeterministiccombinatorialoptimization

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

Mader's S-path packing asks for the maximum number of vertex-disjoint paths whose endpoints lie in distinct blocks of a prescribed partition of the terminals. This paper claims a deterministic algorithm that runs in O(mnk) time, where n is the number of vertices, m the number of edges, and k the number of terminals. The improvement over the previous best deterministic bound O(mn^omega) comes from replacing the costly matrix computations that update an auxiliary dependence graph with a purely combinatorial subroutine that exploits the original S-path structure. Because the algorithm works over a small finite field and only performs simple arithmetic operations, it avoids fast matrix multiplication entirely.

What carries the argument

The dependence matrix D(B) = (d(w,b)) records, for every line element w not in the feasible base B, the unique coefficients expressing w as a linear combination of the vectors in B. The algorithm computes D(B) combinatorially: it roots each connected component of the forest G[B] at a terminal, propagates coefficient vectors c(v^circ,b) and c(v^bullet,b) along tree edges using the walk identities of Lemma 1, and assembles the edge-twin representations from the end-vertex coefficients. This traversal replaces the matrix inversion and multiplication that the generic Gabow-Stallmann update would require.

What would settle it

Compute, on all graphs with up to about seven vertices, both the dependence matrix returned by Algorithm 3 and the true coordinate matrix obtained by Gaussian elimination over F_q; any entry mismatch, or any base on which AugmentOrMaximum fails to return an optimal base, refutes the claimed correctness and time bound.

Watch

Extended reading notes

Core claim

The central claim, stated as Theorem 1, is that Mader's S-path packing problem admits a deterministic algorithm with running time O(mnk). The algorithm reduces the problem to linear matroid parity via Schrijver's linear representation, starts from a feasible base that contains all terminal singletons, and then repeatedly augments the base using the Gabow-Stallmann augmenting-path method. The key new step is a subroutine that computes the dependence matrix D(B) of the current base B in O(mn) time by traversing each tree of the forest G[B] at most twice, instead of solving a general linear system, so the total cost over at most k/2 augmentations is O(mnk).

Load-bearing premise

The Gabow-Stallmann oracle keeps its O(mn) guarantee when the singletons are chosen as the terminal vectors {t} instead of the original twin copies, an adaptation asserted in Section 3 without a proof.

Editorial extensions

If this is right

If correct, the result improves the deterministic worst-case bound for Mader's S-path packing from O(mn^omega) to O(mnk), which is better for instances where k is small relative to n^omega.
The algorithm runs over a finite field F_q of order q = O(|S|), so its arithmetic operations are elementary and it does not depend on the matrix multiplication exponent.
Each augmentation increases the number of lines in the feasible base by exactly one, and at most floor(k/2) augmentations suffice, so the O(mn) per-iteration cost yields the claimed total.
The final S-path packing is recovered in O(n) time from the optimal base, so the whole pipeline remains linear in the graph size outside the dependence-matrix computation.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The combinatorial dependence-matrix update likely extends to the weighted version of S-path packing, since weighted linear matroid parity algorithms also need such matrix information and might now avoid fast matrix multiplication.
The traversal technique may adapt to non-zero A-path packing on group-labelled graphs, where terminals carry labels similar to the block scalars theta(t), potentially yielding a comparable improvement over matrix-based approaches.
A concrete stress test is to verify Algorithm 3 on all small graphs by comparing its output against direct Gaussian elimination, because the paper asserts the traversal invariant without a formal proof.

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.

Desk Editor's Note

read the letter

Short version: the paper has a genuinely new idea—replacing matrix multiplication in the dependence-matrix update with tree traversals in the original graph—and a clean O(mnk) deterministic bound for Mader's S-path packing, but two load-bearing gaps need to be nailed down before I'd bet on it.

What's new: The reduction to linear matroid parity is standard (Schrijver). The contribution is a combinatorial subroutine that computes the dependence matrix for a feasible base by traversing the forest G[B] rooted at terminals, using the fact that a feasible base corresponds to a forest. If correct, this avoids the O(mn^{ω-1}) matrix operations per augmentation and yields the O(mnk) total. Lemmas 1–4 characterize feasible bases cleanly and their proofs are solid. The complexity accounting is careful and the O(mn) space bound is a plus.

Soft spots: The stress-test is on target. Proposition 2 asserts that Gabow-Stallmann's augmenting-path oracle works when the singletons are the terminal vectors t and θ(t)t rather than copies of all twins in L. The paper justifies this with a paragraph saying the singletons are 'dummy vectors' and replacing them 'preserves every guarantee in their proof.' That may be true, but it is not proved or referenced, and the proof in [11] likely uses the specific span-L setting. A referee should check whether the exchange-graph arguments go through verbatim. Second, Proposition 3 (correctness of the main algorithm) is asserted, and Algorithm 3's correctness is only sketched. No invariants are stated for the two-pass traversal, and the transition between tentative and correct representations is not fully formal. Both gaps are addressable, and I don't see an obvious error, but they are load-bearing.

Bottom line: If the gaps are filled, this is a solid result—the first deterministic improvement over O(mn^ω) for Mader's problem. As it stands, it is a promising manuscript that deserves a serious referee, not a desk reject. I'd send it to review and ask for the missing proofs.

Referee Report

2 major / 4 minor

Summary. The paper presents a deterministic algorithm for Mader's S-path packing problem that runs in O(mnk) time, where n=|V|, m=|E|, and k=|T|. The algorithm uses the known reduction of the problem to linear matroid parity and the augmenting-path framework of Gabow and Stallmann, but replaces the repeated computation of the dependence matrix via matrix multiplication with a combinatorial traversal of the current feasible base. The main theorem, Theorem 1, is derived from a series of lemmas about feasible bases, an oracle for augmentation (Proposition 2), a subroutine for computing the dependence matrix (Algorithm 3), and a final subroutine that recovers an S-path packing. The claimed running time improves the previous best deterministic O(mn^omega) bound.

Significance. If the main theorem is correct, the O(mnk) deterministic algorithm is a genuine improvement over the previous O(mn^omega) deterministic bound for Mader's S-path packing, and it shows that the special structure of the matroid parity instance can be exploited to avoid matrix multiplication in the dependence-matrix update. The paper also contains a clean and mostly rigorous treatment of the reduction (Lemmas 1-4) and a plausible combinatorial subroutine for the dependence matrix. However, two load-bearing proof gaps must be closed before the result is established: the adaptation of the Gabow-Stallmann oracle to the modified singleton set is asserted without proof, and the correctness of Algorithm 3 is only sketched. These are addressable issues rather than demonstrated errors.

major comments (2)

[Section 3, Proposition 2] Proposition 2 is the central oracle on which both correctness and the O(mnk) bound depend, but its adaptation to the paper's setting is not proved. The manuscript notes that the original Gabow-Stallmann setting uses copies of all individual twins in L as singletons, whereas here the singletons are the terminal vectors K={t : t in T} together with the relation t* = theta(t)t, and it asserts in one paragraph that this replacement preserves every guarantee because the singletons are only dummy vectors. This is not sufficient: the correctness of the augmenting-path search and its O(mn) time bound in [11] may rely on the specific structure of the original singleton copies, including how they interact with the exchange graph and the feasibility certificate. The authors should either cite a theorem in [11] that covers exactly this setting, or provide a self-contained proof that the augmenting-path exchange lemmas remain valid when the dummy singletons are replaced by K. Since Proposition 2 is used in Proposition 4 and Theorem 1, this gap is load-bearing.
[Section 4 (Proposition 3) and Algorithm 3] Proposition 3 asserts that Algorithm 1 correctly solves Mader's problem, but no formal proof is given for the correctness of Algorithm 3, the computation of the dependence matrix. Section 4.2 describes the traversal informally, but it does not state or prove the invariant satisfied by the maintained values c(w,b), nor does it prove that the transition rules in lines 19-27 and the correction formulas in lines 9-13 produce the unique representation (34) with respect to B. In particular, the two-terminal component case, where Z∩T[B]=empty, is the delicate part and is only sketched. A proper proof should show that the first traversal computes the tentative representation of v°-t1 and v•-t1, that the formula for the representation of t2 is correct, and that the second traversal propagates the correct representations. Without such an invariant, the correctness of the O(mn) dependence-matrix computation is not established, and consequently Proposition 3 does not follow from the text.

minor comments (4)

[Section 3, first paragraph] The sentence 'repeatedly updates the feasible base B with E[B] increased by 2 (and hence T[B] decreased by 1) per iteration' is inconsistent with Eq. (18) and with the symmetric-difference equations (31)-(32), which show that |E[B]| increases by 1 and |T[B]| decreases by 2 per augmentation.
[Algorithm 2, line 7] The instruction 'R←R∪e' should read 'R←R∪{u,v}' where e={u,v}, since e is an edge and not a set of vertices.
[Algorithm 3, lines 11-12] The update of c(t•,b) in line 12 uses c(t◦,b) after it has already been overwritten in line 11; the authors should state explicitly whether the assignments are meant to be sequential or simultaneous, and if sequential, confirm that the new value is intended.
[Section 4.2] The phrase 'tentative representation of v°−t1, v•−t1' is not defined formally; the authors should define exactly which vectors the entries c(w,b) represent during the first traversal from a root that is not in B.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the algorithm's claims rest on external black-box results and a stated but unproved adaptation that is a correctness gap, not a circular reduction.

full rationale

The paper's derivation chain is: Schrijver's reduction (Prop. 1, external [39]) maps Mader's problem to finding a feasible base maximizing lines; Gabow-Stallmann's augmenting-path oracle (Prop. 2, external [11]) supplies O(mn) time per augmentation; and the new subroutine ComputeDependence (Algorithm 3) computes the dependence matrix in O(mn) time using the forest structure of the feasible base. None of these steps defines its conclusion in terms of itself. There are no fitted parameters, no predictions, and no quantity is normalized so that the target equality holds by construction. The only passages that could raise concern are Section 3's explicit remark that Gabow-Stallmann's original singletons differ from the terminal singletons used here, followed by the assertion that 'replacing these singletons still preserves every guarantee in their proof,' and Proposition 3's correctness claim for Algorithm 1 without a formal invariant for Algorithm 3. These are unproved assumptions and legitimate correctness risks, but they are not circularity: the O(mn) oracle is taken from an external 1986 paper rather than derived from Theorem 1 or from this paper's own equations, and the paper does not use a self-citation chain to force its choice. Accordingly the score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The algorithm relies on the standard matroid-parity reformulation and on the Gabow-Stallmann augmentation oracle; no free parameters or invented entities are introduced by this paper. The main unstated load is the unproved adaptation of the oracle to the terminal-singleton setting.

assumptions (4)

standard math Schrijver's linear representation of Mader's problem is valid (Proposition 1, Section 2).
The reduction is cited to [39] and supported by Lemmas 1-4 in the paper; it is the standard foundation for matroid-parity algorithms.
domain assumption Gabow-Stallmann augmenting-path algorithm (Proposition 2) runs in O(mn) per augmentation and remains correct when singletons are terminal vectors rather than copies of all twins.
The paper states the original setting differs from Section 2 and asserts replacement preserves guarantees without proof; the per-iteration time and correctness of the loop depend on this.
standard math Bertrand's postulate: for |S| >= 2 there is a prime q with |S| < q <= 2|S|.
Used to choose the field F_q in Section 2; well-established.
domain assumption Uniform-cost model: arithmetic operations over F_q run in constant time.
Adopted in Section 1 and Section 5; the O(mnk) bound is stated in this model.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Faster Deterministic Algorithm for Mader's $\mathcal{S}$-Path Packing." pith.science (2026). https://pith.science/paper/VNT6H7MI

@misc{pith2026241118292,
  author       = {Pith},
  title        = {Pith review of: A Faster Deterministic Algorithm for Mader's $\mathcalS$-Path Packing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VNT6H7MI}},
  note         = {Machine review of arXiv:2411.18292}
}

abstract

Given an undirected graph $G = (V,E)$ with a set of terminals $T\subseteq V$ partitioned into a family $\mathcal{S}$ of disjoint blocks, find the maximum number of vertex-disjoint paths whose endpoints belong to two distinct blocks while no other internal vertex is a terminal. This problem is called Mader's $\mathcal{S}$-path packing. It has been of remarkable interest as a common generalization of the non-bipartite matching and vertex-disjoint $s\text{-}t$ paths problem. This paper presents a new deterministic algorithm for this problem via known reduction to linear matroid parity. The algorithm utilizes the augmenting-path algorithm of Gabow and Stallmann (1986), while replacing costly matrix operations between augmentation steps with a faster algorithm that exploits the original $\mathcal{S}$-path packing instance. The proposed algorithm runs in $O(mnk)$ time, where $n = |V|$, $m = |E|$, and $k = |T|\le n$. This improves on the previous best bound $O(mn^{\omega})$ for deterministic algorithms, where $\omega\ge2$ denotes the matrix multiplication exponent.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

46 extracted references · 45 canonical work pages

[11]

Gabow and Matthias Stallmann

Harold N. Gabow and Matthias Stallmann. An augmenting path algo rithm for linear matroid parity. Combinatorica, 6(2):123–150, 1986

work page 1986
[1]

Aho, John E

Alfred V. Aho, John E. Hopcroft, and Jeﬀrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974

work page 1974
[2]

Maxim A. Babenko. A fast algorithm for the path 2-packing proble m. Theory of Computing Systems , 46(1):59–79, 2009

work page 2009
[3]

Greedy algorithm and symmetric matroids

Andr´ e Bouchet. Greedy algorithm and symmetric matroids. Mathematical Programming, 38:147–159, 1987

work page 1987
[4]

Ramaswamy Chandrasekaran and Santosh N. Kabadi. Pseudoma troids. Discrete Mathematics , 71(3):205–217, 1988

work page 1988
[5]

Algebraic algorit hms for linear matroid parity problems

Ho Yee Cheung, Lap Chi Lau, and Kai Man Leung. Algebraic algorit hms for linear matroid parity problems. ACM Transactions on Algorithms (TALG) , 10(3):1–26, 2014

work page 2014
[6]

Cunningham, and Jim Geelen

Maria Chudnovsky, William H. Cunningham, and Jim Geelen. An algorith m for packing non-zero A-paths in group-labelled graphs. Combinatorica, 28(2):145–161, 2008

work page 2008
[7]

Packing non-zero A-paths in group-labelled graphs

Maria Chudnovsky, Jim Geelen, Bert Gerards, Luis Goddyn, Micha el Lohman, and Paul Seymour. Packing non-zero A-paths in group-labelled graphs. Combinatorica, 26:521–532, 2006

work page 2006

Show all 46 references

[8]

Paths, trees, and ﬂowers

Jack Edmonds. Paths, trees, and ﬂowers. Canadian Journal of Mathematics , 17:449–467, 1965. 10

1965
[9]

An O(N 2

Shimon Even and Oded Kariv. An O(N 2. 5) algorithm for maximum matching in general graphs. In Proceedings of the 16th Annual Symposium on Foundations of C omputer Science (FOCS) , pages 100– 112, 1975

1975
[10]

Harold N. Gabow. An eﬃcient implementation of Edmonds’ algorith m for maximum matching on graphs. Journal of the ACM (JACM) , 23(2):221–234, 1976

1976
[12]

Maximum-minimum S¨ atze und verallgemeinerte Faktoren von Graphen

Tibor Gallai. Maximum-minimum S¨ atze und verallgemeinerte Faktoren von Graphen. Acta Mathematica Hungarica, 12(1-2):131–173, 1961

1961
[13]

Nicholas J. A. Harvey. Algebraic algorithms for matching and mat roid problems. SIAM Journal on Computing, 39(2):679–702, 2009

2009
[14]

A dual descent algorithm for node-capacitated m ultiﬂow problems and its applications

Hiroshi Hirai. A dual descent algorithm for node-capacitated m ultiﬂow problems and its applications. ACM Transactions on Algorithms (TALG) , 15(1):1–24, 2018

2018
[15]

Tree metrics and edge-disjoint S-paths

Hiroshi Hirai and Gyula Pap. Tree metrics and edge-disjoint S-paths. Mathematical Programming, 147(1):81–123, 2014

2014
[16]

A weighted linear matroid p arity algorithm

Satoru Iwata and Yusuke Kobayashi. A weighted linear matroid p arity algorithm. SIAM Journal on Computing, 51(2):STOC17–238, 2021

2021
[17]

Finding maximum edge-disjoint paths between multiple terminals

Satoru Iwata and Yu Yokoi. Finding maximum edge-disjoint paths between multiple terminals. SIAM Journal on Computing , 52(5):1230–1268, 2023

2023
[18]

0/1/all C SPs, half-integral A-path packing, and linear-time FPT algorithms

Yoichi Iwata, Yutaro Yamaguchi, and Yuichi Yoshida. 0/1/all C SPs, half-integral A-path packing, and linear-time FPT algorithms. In Proceedings of the 59th IEEE Annual Symposium on Foundation s of Computer Science (FOCS) , pages 462–473. IEEE, 2018

2018
[19]

Karzanov

Alexander V. Karzanov. Edge-disjoint T -paths of minimum total cost. Technical Report STAN-CS-92- 1465, Department of Computer Science, Stanford University, 19 93
[20]

Karzanov

Alexander V. Karzanov. Multiﬂows and disjoint paths of minimum t otal cost. Mathematical Program- ming: Series A and B , 78(2):219–242, 1997

1997
[21]

Faster algorithms on lin ear delta-matroids

Tomohiro Koana and Magnus Wahlstr¨ om. Faster algorithms on lin ear delta-matroids. arXiv preprint arXiv:2402.11596, 2024

2024 arXiv
[22]

The dependence graph for bases in matroids

Stein Krogdahl. The dependence graph for bases in matroids. Discrete Mathematics, 19(1):47–59, 1977

1977
[23]

Eugene L. Lawler. Combinatorial Optimization: Networks and Matroids . Holt, Rinehart and Winston, 1976

1976
[24]

A note on factor-critical graphs.Studia Sci

L´ aszl´ o Lov´ asz. A note on factor-critical graphs.Studia Sci. Math. Hungar , 7(11):279–280, 1972

1972
[25]

The matroid matching problem.Algebraic Methods in Graph Theory , 2:495–517, 1978

L´ aszl´ o Lov´ asz. The matroid matching problem.Algebraic Methods in Graph Theory , 2:495–517, 1978

1978
[26]

Matroid matching and some applications.Journal of Combinatorial Theory, Series B , 28(2):208–236, 1980

L´ aszl´ o Lov´ asz. Matroid matching and some applications.Journal of Combinatorial Theory, Series B , 28(2):208–236, 1980

1980
[27]

¨Uber die Maximalzahl kreuzungsfreier H-Wege

Wolfgang Mader. ¨Uber die Maximalzahl kreuzungsfreier H-Wege. Archiv der Mathematik , 31(1):387– 402, 1978

1978
[28]

John H. Mason. On a class of matroids arising from paths in graph s. Proceedings of the London Mathematical Society, 3(1):55–74, 1972

1972
[29]

Mader matroids are gammoids

Gyula Pap. Mader matroids are gammoids. Technical Report TR- 2006-17, Egerv´ ary Research Group on Combinatorial Optimization (EGRES), 2006. 11

2006
[30]

Packing non-returning A-paths

Gyula Pap. Packing non-returning A-paths. Combinatorica, 27(2):247–251, 2007

2007
[31]

Some new results on node-capacitated packing of A-paths

Gyula Pap. Some new results on node-capacitated packing of A-paths. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC) , pages 599–604, 2007

2007
[32]

Packing non-returning A-paths algorithmically

Gyula Pap. Packing non-returning A-paths algorithmically. Discrete Mathematics , 308(8):1472–1488, 2008

2008
[33]

Strongly polynomial time solvability of integral and half -integral node-capacitated multiﬂow problems

Gyula Pap. Strongly polynomial time solvability of integral and half -integral node-capacitated multiﬂow problems. Technical Report TR-2008-12, Egerv´ ary Research G roup on Combinatorial Optimization (EGRES), 2008

2008
[34]

A polynomial time algorithm for weighted node-disjoint S-paths

Gyula Pap. A polynomial time algorithm for weighted node-disjoint S-paths. In Proceedings of the 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, pages 322–331, 2011

2011
[35]

Weighted linear matroid matching

Gyula Pap. Weighted linear matroid matching. In Proceedings the 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications , pages 411–413, 2013

2013
[36]

Weighted bipartite matching in matrix multiplicatio n time

Piotr Sankowski. Weighted bipartite matching in matrix multiplicatio n time. In Proceedings of the 33rd international conference on Automata, Languages and Progr amming-Volume Part I , pages 274–285, 2006

2006
[37]

Is each mader matroid a gammoid? https://homepages.cwi.nl/~lex/, 2001

Alexander Schrijver. Is each mader matroid a gammoid? https://homepages.cwi.nl/~lex/, 2001

2001
[38]

A short proof of Mader’s S-paths theorem

Alexander Schrijver. A short proof of Mader’s S-paths theorem. Journal of Combinatorial Theory, Series B , 82(2):319–321, 2001

2001
[39]

Combinatorial Optimization: Polyhedra and Eﬃciency

Alexander Schrijver. Combinatorial Optimization: Polyhedra and Eﬃciency . Springer-Verlag, 2003

2003
[40]

The path-packing structure of graphs

Andr´ as Seb˝ o and L´ aszl´ o Szeg˝ o. The path-packing structure of graphs. In Proceedings of the 10th International Conference on Integer Programming and Combi natorial Optimization (IPCO) , pages 256–
[41]

Packing non-zero A-paths via matroid matching

Shin-ichi Tanigawa and Yutaro Yamaguchi. Packing non-zero A-paths via matroid matching. Discrete Applied Mathematics, 214:169–178, 2016

2016
[42]

A 4k2 kernel for feedback vertex set

St´ ephan Thomass´ e. A 4k2 kernel for feedback vertex set. ACM Transactions on Algorithms (TALG) , 6(2):1–8, 2010

2010
[43]

Representative set statements for delt a-matroids and the Mader delta-matroid

Magnus Wahlstr¨ om. Representative set statements for delt a-matroids and the Mader delta-matroid. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discre te Algorithms (SODA) , pages 780–810. SIAM, 2024

2024
[44]

New bounds for matrix multiplication: from alpha to omega

Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zho u. New bounds for matrix multiplication: from alpha to omega. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 3792–3835. SIAM, 2024

2024
[45]

Packing A-paths in group-labelled graphs via linear matroid parity

Yutaro Yamaguchi. Packing A-paths in group-labelled graphs via linear matroid parity. SIAM Journal on Discrete Mathematics , 30(1):474–492, 2016

2016
[46]

Shortest disjoint S-paths via weighted linear matroid parity

Yutaro Yamaguchi. Shortest disjoint S-paths via weighted linear matroid parity. In Proceedings of the 27th International Symposium on Algorithms and Computa tion (ISAAC) . Schloss-Dagstuhl-Leibniz Zentrum f¨ ur Informatik, 2016. 12

2016

Pith tools

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

[1] [11]

Gabow and Matthias Stallmann

Harold N. Gabow and Matthias Stallmann. An augmenting path algo rithm for linear matroid parity. Combinatorica, 6(2):123–150, 1986

work page 1986

[2] [1]

Aho, John E

Alfred V. Aho, John E. Hopcroft, and Jeﬀrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974

work page 1974

[3] [2]

Maxim A. Babenko. A fast algorithm for the path 2-packing proble m. Theory of Computing Systems , 46(1):59–79, 2009

work page 2009

[4] [3]

Greedy algorithm and symmetric matroids

Andr´ e Bouchet. Greedy algorithm and symmetric matroids. Mathematical Programming, 38:147–159, 1987

work page 1987

[5] [4]

Ramaswamy Chandrasekaran and Santosh N. Kabadi. Pseudoma troids. Discrete Mathematics , 71(3):205–217, 1988

work page 1988

[6] [5]

Algebraic algorit hms for linear matroid parity problems

Ho Yee Cheung, Lap Chi Lau, and Kai Man Leung. Algebraic algorit hms for linear matroid parity problems. ACM Transactions on Algorithms (TALG) , 10(3):1–26, 2014

work page 2014

[7] [6]

Cunningham, and Jim Geelen

Maria Chudnovsky, William H. Cunningham, and Jim Geelen. An algorith m for packing non-zero A-paths in group-labelled graphs. Combinatorica, 28(2):145–161, 2008

work page 2008

[8] [7]

Packing non-zero A-paths in group-labelled graphs

Maria Chudnovsky, Jim Geelen, Bert Gerards, Luis Goddyn, Micha el Lohman, and Paul Seymour. Packing non-zero A-paths in group-labelled graphs. Combinatorica, 26:521–532, 2006

work page 2006