Abstract
Mader's disjoint Spaths problem unifies two generalizations of bipartite matching: (a) nonbipartite 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) nonbipartite 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 designatedsize 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 polynomialtime 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 nonzero Apaths in grouplabeled 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.
BibTeX  Entry
@InProceedings{yamaguchi:LIPIcs:2016:6832,
author = {Yutaro Yamaguchi},
title = {{Shortest Disjoint SPaths Via Weighted Linear Matroid Parity}},
booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)},
pages = {63:163:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770262},
ISSN = {18688969},
year = {2016},
volume = {64},
editor = {SeokHee Hong},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6832},
URN = {urn:nbn:de:0030drops68325},
doi = {10.4230/LIPIcs.ISAAC.2016.63},
annote = {Keywords: Mader's Spaths, packing nonzero Apaths in grouplabeled graphs, linear matroid parity, weighted problems, tractability}
}
Keywords: 

Mader's Spaths, packing nonzero Apaths in grouplabeled graphs, linear matroid parity, weighted problems, tractability 
Collection: 

27th International Symposium on Algorithms and Computation (ISAAC 2016) 
Issue Date: 

2016 
Date of publication: 

07.12.2016 