Document Open Access Logo

Shortest Disjoint S-Paths Via Weighted Linear Matroid Parity

Author Yutaro Yamaguchi

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.63.pdf
  • Filesize: 408 kB
  • 13 pages

Document Identifiers

Author Details

Yutaro Yamaguchi

Cite As Get BibTex

Yutaro Yamaguchi. Shortest Disjoint S-Paths Via Weighted Linear Matroid Parity. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 63:1-63:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ISAAC.2016.63

Abstract

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.

Subject Classification

Keywords
  • Mader's S-paths
  • packing non-zero A-paths in group-labeled graphs
  • linear matroid parity
  • weighted problems
  • tractability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. Björklund and T. Husfeldt. Shortest two disjoint paths in polynomial time. In Proceedings of ICALP 2014, pages 211-222, 2014. Google Scholar
  2. P. M. Camerini, G. Galbiati, and F. Maffioli. Random pseudo-polynomial algorithms for exact matroid problems. Journal of Algorithms, 13(2):258-273, 1992. Google Scholar
  3. H. Y. Cheung, L. C. Lau, and K. M. Leung. Algebraic algorithms for linear matroid parity problems. ACM Transactions on Algorithms, 10(3):No. 10, 2014. Google Scholar
  4. M. Chudnovsky, W. H. Cunningham, and J. Geelen. An algorithm for packing non-zero A-paths in group-labelled graphs. Combinatorica, 28(2):145-161, 2008. Google Scholar
  5. M. Chudnovsky, J. Geelen, B. Gerards, L. Goddyn, M. Lohman, and P. Seymour. Packing non-zero A-paths in group-labelled graphs. Combinatorica, 26(5):521-532, 2006. Google Scholar
  6. A. Dress and L. Lovász. On some combinatorial properties of algebraic matroids. Combinatorica, 7(1):39-48, 1987. Google Scholar
  7. H. N. Gabow and M. Stallmann. An augmenting path algorithm for linear matroid parity. Combinatorica, 6(2):123-150, 1986. Google Scholar
  8. T. Gallai. Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen. Acta Mathematica Academiae Scientiarum Hungaricae, 12(1):131-173, 1961. Google Scholar
  9. H. Hirai and H. Namba. Shortest (A + B)-path packing via hafnian. arXiv preprints, arXiv:1603.08073, 2016. Google Scholar
  10. H. Hirai and G. Pap. Tree metrics and edge-disjoint S-paths. Mathematical Programming, Ser. A, 147(1):81-123, 2014. Google Scholar
  11. S. Iwata. A weighted linear matroid parity algorithm. In Proceedings of the 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, pages 251-259, 2013. Google Scholar
  12. A. V. Karzanov. Edge-disjoint T-paths of minimum total cost. Technical Report STAN-CS-92-1465, Department of Computer Science, Stanford University, 1993. Google Scholar
  13. A. V. Karzanov. Multiflows and disjoint paths of minimum total cost. Mathematical Programming, 78(2):219-242, 1997. Google Scholar
  14. Y. Kobayashi and S. Toyooka. Finding a shortest non-zero path in group-labeled graphs via permanent computation. Algorithmica, to appear. Google Scholar
  15. E. L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, 1976. Google Scholar
  16. L. Lovász. Matroid matching and some applications. Journal of Combinatorial Theory, Ser. B, 28(2):208-236, 1980. Google Scholar
  17. L. Lovász. The matroid matching problem. Algebraic Methods in Graph Theory: Colloquia Mathematica Societatis János Bolyai, 25(2):495-517, 1981. Google Scholar
  18. L. Lovász and M. D. Plummer. Matching Theory. Akadémiai Kiadó, 1986. Google Scholar
  19. W. Mader. Über die Maximalzahl kreuzungsfreierH-Wege. Archiv der Mathematik, 31(1):387-402, 1978. Google Scholar
  20. J. B. Orlin. A fast, simpler algorithm for the matroid parity problem. In Proceedings of IPCO 2008, pages 240-258, 2008. Google Scholar
  21. G. 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. Google Scholar
  22. G. Pap. Weighted linear matroid matching. In Proceedings of the 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, pages 411-413, 2013. Google Scholar
  23. A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer-Verlag, 2003. Google Scholar
  24. S. Tanigawa and Y. Yamaguchi. Packing non-zero A-paths via matroid matching. Discrete Applied Mathematics, 214(11):169-178, 2016. Google Scholar
  25. Y. Yamaguchi. Packing A-paths in group-labelled graphs via linear matroid parity. SIAM Journal on Discrete Mathematics, 30(1):474-492, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact