2026-07-21T23:33:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6832 2024-03-06T10:38:59Z ddc:004 open_access

Shortest Disjoint S-Paths Via Weighted Linear Matroid Parity Yamaguchi, Yutaro Mader's S-paths packing non-zero A-paths in group-labeled graphs linear matroid parity weighted problems tractability Mader's disjoint S-paths problem unifies two generalizations of bipartite matching: (a) non-bipartite matching and (b) disjoint s–t paths. Lovász (1980, 1981) first proposed an efficient algorithm for this problem via a reduction to matroid matching, which also unifies two generalizations of bipartite matching: (a) non-bipartite matching and (c) matroid intersection. While the weighted versions of the problems (a)-(c) in which we aim to minimize the total weight of a designated-size feasible solution are known to be solvable in polynomial time, the tractability of such a weighted version of Mader's problem has been open for a long while. In this paper, we present the first solution to this problem with the aid of a linear representation for Lovász' reduction (which leads to a reduction to linear matroid parity) due to Schrijver (2003) and polynomial-time algorithms for a weighted version of linear matroid parity announced by Iwata (2013) and by Pap (2013). Specifically, we give a reduction of the weighted version of Mader's problem to weighted linear matroid parity, which leads to an O(n^5)-time algorithm for the former problem, where n denotes the number of vertices in the input graph. Our reduction technique is also applicable to a further generalized framework, packing non-zero A-paths in group-labeled graphs, introduced by Chudnovsky, Geelen, Gerards, Goddyn, Lohman, and Seymour (2006). The extension leads to the tractability of a broader class of weighted problems not restricted to Mader’s setting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yutaro Yamaguchi 2016 Is Part Of LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2016.63 urn:nbn:de:0030-drops-68325 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.63 eng https://creativecommons.org/licenses/by/3.0/legalcode