Document Open Access Logo

The b-Matching Problem in Distance-Hereditary Graphs and Beyond

Authors Guillaume Ducoffe, Alexandru Popa

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.30.pdf
  • Filesize: 0.52 MB
  • 13 pages

Document Identifiers

Author Details

Guillaume Ducoffe
  • ICI – National Institute for Research and Development in Informatics, Bucharest, Romania , The Research Institute of the University of Bucharest ICUB, Bucharest, Romania
Alexandru Popa
  • University of Bucharest, Bucharest, Romania , ICI – National Institute for Research and Development in Informatics, Bucharest, Romania

Funding

This work was supported by the Institutional research programme PN 1819 "Advanced IT resources to support digital transformation processes in the economy and society - RESINFO-TD" (2018), project PN 1819-01-01 "Modeling, simulation, optimization of complex systems and decision support in new areas of IT&C research", funded by the Ministry of Research and Innovation, Romania.

Cite AsGet BibTex

Guillaume Ducoffe and Alexandru Popa. The b-Matching Problem in Distance-Hereditary Graphs and Beyond. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 30:1-30:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.30

Abstract

We make progress on the fine-grained complexity of Maximum-Cardinality Matching on graphs of bounded clique-width. Quasi linear-time algorithms for this problem have been recently proposed for the important subclasses of bounded-treewidth graphs (Fomin et al., SODA'17) and graphs of bounded modular-width (Coudert et al., SODA'18). We present such algorithm for bounded split-width graphs - a broad generalization of graphs of bounded modular-width, of which an interesting subclass are the distance-hereditary graphs. Specifically, we solve Maximum-Cardinality Matching in O((k log^2{k})*(m+n) * log{n})-time on graphs with split-width at most k. We stress that the existence of such algorithm was not even known for distance-hereditary graphs until our work. Doing so, we improve the state of the art (Dragan, WG'97) and we answer an open question of (Coudert et al., SODA'18). Our work brings more insights on the relationships between matchings and splits, a.k.a., join operations between two vertex-subsets in different connected components. Furthermore, our analysis can be extended to the more general (unit cost) b-Matching problem. On the way, we introduce new tools for b-Matching and dynamic programming over split decompositions, that can be of independent interest.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
  • Theory of computation → Design and analysis of algorithms
Keywords
  • maximum-cardinality matching
  • b-matching
  • FPT in P
  • split decomposition
  • distance-hereditary graphs

Metrics

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

Related Versions

References

  1. H.-J. Bandelt and H. Mulder. Distance-hereditary graphs. J. of Combinatorial Theory, Series B, 41(2):182-208, 1986. Google Scholar
  2. C. Berge. Two theorems in graph theory. Proceedings of the National Academy of Sciences, 43(9):842-844, 1957. Google Scholar
  3. J. A. Bondy and U. S. R. Murty. Graph theory. Grad. Texts in Math., 2008. Google Scholar
  4. P. Charbit, F. De Montgolfier, and M. Raffinot. Linear time split decomposition revisited. SIAM J. on Discrete Mathematics, 26(2):499-514, 2012. Google Scholar
  5. D. Coudert, G. Ducoffe, and A. Popa. Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. In SODA'18, pages 2765-2784. SIAM, 2018. Google Scholar
  6. W. Cunningham. Decomposition of directed graphs. SIAM Journal on Algebraic Discrete Methods, 3(2):214-228, 1982. Google Scholar
  7. F. Dragan. On greedy matching ordering and greedy matchable graphs. In WG'97, volume 1335 of LNCS, pages 184-198. Springer, 1997. Google Scholar
  8. F. Dragan and F. Nicolai. LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem. Discrete Applied Mathematics, 98(3):191-207, 2000. Google Scholar
  9. G. Ducoffe and A. Popa. A quasi linear-time b-Matching algorithm on distance-hereditary graphs and bounded split-width graphs. Technical Report arXiv:1804.09393, arXiv, 2018. Google Scholar
  10. G. Ducoffe and A. Popa. The use of a pruned modular decomposition for Maximum Matching algorithms on some graph classes. In ISAAC, 2018. To appear. Google Scholar
  11. J. Edmonds. Paths, trees, and flowers. Canadian J. of mathematics, 17(3):449-467, 1965. Google Scholar
  12. J. Edmonds and E. Johnson. Matching: A well-solved class of integer linear programs. In Combinatorial structures and their applications. Citeseer, 1970. Google Scholar
  13. F. Fomin, D. Lokshtanov, M. Pilipczuk, S. Saurabh, and M. Wrochna. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. In SODA'17, pages 1419-1432. SIAM, 2017. Google Scholar
  14. H. Gabow. An Efficient Reduction Technique for Degree-Constrained Subgraph and Bidirected Network Flow Problems. In STOC'83, pages 448-456. ACM, 1983. Google Scholar
  15. H. Gabow. Data Structures for Weighted Matching and Extensions to b-matching and f-factors. arXiv, 2016. URL: http://arxiv.org/abs/1611.07541.
  16. A. C. Giannopoulou, G. B. Mertzios, and R. Niedermeier. Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs. Theoretical Computer Science, 689:67-95, 2017. Google Scholar
  17. M. Golumbic and U. Rotics. On the clique-width of some perfect graph classes. International J. of Foundations of Computer Science, 11(03):423-443, 2000. Google Scholar
  18. J. Hopcroft and R. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing, 2(4):225-231, 1973. Google Scholar
  19. Y. Iwata, T. Ogasawara, and N. Ohsaka. On the Power of Tree-Depth for Fully Polynomial FPT Algorithms. In STACS'18, 2018. Google Scholar
  20. S. Kratsch and F. Nelles. Efficient and adaptive parameterized algorithms on modular decompositions. In ESA'18. LIPIcs, 2018. To appear. Google Scholar
  21. G. Mertzios, A. Nichterlein, and R. Niedermeier. The Power of Linear-Time Data Reduction for Maximum Matching. In MFCS'17, pages 46:1-46:14, 2017. Google Scholar
  22. S. Micali and V. Vazirani. An O(√V E) Algorithm for Finding Maximum Matching in General Graphs. In FOCS'80, pages 17-27. IEEE, 1980. Google Scholar
  23. M. Rao. Solving some NP-complete problems using split decomposition. Discrete Applied Mathematics, 156(14):2768-2780, 2008. Google Scholar
  24. L. Roditty and V. Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In STOC'13, pages 515-524. ACM, 2013. Google Scholar
  25. W. Tutte. A short proof of the factor theorem for finite graphs. Canad. J. Math, 6(1954):347-352, 1954. Google Scholar
  26. M.-S. Yu and C.-H. Yang. An O(n)-time algorithm for maximum matching on cographs. Information processing letters, 47(2):89-93, 1993. 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 Imprint Privacy Contact