Document Open Access Logo

Maximum Matching in Almost Linear Time on Graphs of Bounded Clique-Width

Author Guillaume Ducoffe

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2021.15.pdf
  • Filesize: 0.79 MB
  • 17 pages

Document Identifiers

Author Details

Guillaume Ducoffe
  • National Institute for Research and Development in Informatics, Bucharest, Romania
  • University of Bucharest, Romania

Funding

This work was supported by Grant TC ICUB-SSE 15109-26.07.2021, "The complexity landscape of Maximum Matching". It was also supported by project PN-19-37-04-01 "New solutions for complex problems in current ICT research fields based on modelling and optimization", funded by the Romanian Core Program of the Ministry of Research and Innovation (MCI) 2019-2022.

Cite As Get BibTex

Guillaume Ducoffe. Maximum Matching in Almost Linear Time on Graphs of Bounded Clique-Width. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.IPEC.2021.15

Abstract

Recently, independent groups of researchers have presented algorithms to compute a maximum matching in Õ(f(k) ⋅ (n+m)) time, for some computable function f, within the graphs where some clique-width upper bound is at most k (e.g., tree-width, modular-width and P₄-sparseness). However, to the best of our knowledge, the existence of such algorithm within the graphs of bounded clique-width has remained open until this paper. Indeed, we cannot even apply Courcelle’s theorem to this problem directly, because a matching cannot be expressed in MSO₁ logic. 
Our first contribution is an almost linear-time algorithm to compute a maximum matching in any bounded clique-width graph, being given a corresponding clique-width expression. It can be used to also compute the Edmonds-Gallai decomposition. For that, we do apply Courcelle’s theorem, but in order to compute the cardinality of a maximum matching rather than the matching itself, via the classic Tutte-Berge formula. To obtain with this approach a maximum matching, we need to combine it with a recursive dissection scheme for bounded clique-width graphs based on the existence of balanced edge-cuts with bounded neighbourhood diversity, and with a distributed version of Courcelle’s theorem (Courcelle and Vanicat, DAM 2016) - of which we present here a slightly stronger version than the standard one in the literature - in order to evaluate the Tutte-Berge formula on various subgraphs of the input.
Finally, for the bipartite graphs of clique-width at most k, we present an alternative Õ(k²⋅(n+m))-time algorithm for the problem. The algorithm is randomized and it is based on a completely different approach than above: combining various reductions to matching and flow problems on bounded tree-width graphs with a very recent result on the parameterized complexity of linear programming (Dong et. al., STOC'21). Our results for bounded clique-width graphs extend many prior works on the complexity of Maximum Matching within cographs, distance-hereditary graphs, series-parallel graphs and other subclasses.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Graph algorithms analysis
Keywords
  • Maximum Matching
  • Maximum b-matching
  • Clique-width
  • Tree-width
  • Courcelle’s theorem
  • FPT in P

Metrics

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

References

  1. Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 377-391. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch28.
  2. J. Alman and V. Vassilevska Williams. A refined laser method and faster matrix multiplication. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 522-539. SIAM, 2021. Google Scholar
  3. N. Anari and V. Vazirani. Matching Is as Easy as the Decision Problem, in the NC Model. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 of Leibniz International Proceedings in Informatics (LIPIcs), pages 54:1-54:25. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2020. Google Scholar
  4. R.P. Anstee. A polynomial algorithm for b-matchings: an alternative approach. Information Processing Letters, 24(3):153-157, 1987. Google Scholar
  5. M. Bentert, T. Fluschnik, A. Nichterlein, and R. Niedermeier. Parameterized aspects of triangle enumeration. Journal of Computer and System Sciences, 103:61-77, 2019. Google Scholar
  6. C. Berge. Sur le couplage maximum dun graphe. COMPTES RENDUS HEBDOMADAIRES DES SEANCES DE L'ACADEMIE DES SCIENCES, 247(3):258-259, 1958. Google Scholar
  7. John Adrian Bondy and Uppaluri Siva Ramachandra Murty. Graph theory, volume 244 of Graduate Texts in Mathematics. Springer-Verlag London, 2008. Google Scholar
  8. M.L. Carmosino, J. Gao, R. Impagliazzo, I. Mihajlin, R. Paturi, and S. Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 261-270, 2016. Google Scholar
  9. M. Chang. Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs. In ISAAC, pages 146-155. Springer, 1996. Google Scholar
  10. J. Cheriyan. Randomized Õ(M(|V|)) Algorithms for Problems in Matching Theory. SIAM Journal on Computing, 26(6):1635-1655, 1997. Google Scholar
  11. V. Cohen-Addad, M. Habib, and F. de Montgolfier. Algorithmic aspects of switch cographs. Discrete Applied Mathematics, 200:23-42, 2016. Google Scholar
  12. Derek G. Corneil and Udi Rotics. On the relationship between clique-width and treewidth. SIAM Journal on Computing, 34(4):825-847, 2005. URL: https://doi.org/10.1137/S0097539701385351.
  13. D. Coudert, G. Ducoffe, and A. Popa. Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. ACM Transactions on Algorithms (TALG), 15(3):1-57, 2019. Google Scholar
  14. B. Courcelle and J. Engelfriet. Graph structure and monadic second-order logic: a language-theoretic approach, volume 138. Cambridge University Press, 2012. Google Scholar
  15. B. Courcelle, J.A. Makowsky, and U. Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Computing Systems, 33(2):125-150, 2000. Google Scholar
  16. B. Courcelle and A. Twigg. Constrained-path labellings on graphs of bounded clique-width. Theory of Computing Systems, 47(2):531-567, 2010. Google Scholar
  17. B. Courcelle and R. Vanicat. Query efficient implementation of graphs of bounded clique-width. Discrete Applied Mathematics, 131(1):129-150, 2003. Google Scholar
  18. Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation, 85(1):12-75, 1990. URL: https://doi.org/10.1016/0890-5401(90)90043-H.
  19. Bruno Courcelle, Pinar Heggernes, Daniel Meister, Charis Papadopoulos, and Udi Rotics. A characterisation of clique-width through nested partitions. Discrete Applied Mathematics, 187:70-81, 2015. URL: https://doi.org/10.1016/j.dam.2015.02.016.
  20. Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs. Discrete Applied Mathematics, 101(1):77-114, 2000. URL: https://doi.org/10.1016/S0166-218X(99)00184-5.
  21. K.K. Dabrowski and D. Paulusma. Classifying the clique-width of H-free bipartite graphs. Discrete Applied Mathematics, 200:43-51, 2016. Google Scholar
  22. E. Dahlhaus and M. Karpinski. Matching and multidimensional matching in chordal and strongly chordal graphs. Discrete Applied Mathematics, 84(1-3):79-91, 1998. Google Scholar
  23. Reinhard Diestel. Graph Theory. Graduate Texts in Mathematics. Springer, 2010. 4th edition. URL: https://doi.org/10.1007/978-3-662-53622-3.
  24. J. Doner. Tree acceptors and some of their applications. Journal of Computer and System Sciences, 4(5):406-451, 1970. Google Scholar
  25. S. Dong, Y.T. Lee, and G. Ye. A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path. In ACM SIGACT Symposium on Theory of Computing (STOC), pages 1784-1797, 2021. Google Scholar
  26. F. Dragan. On greedy matching ordering and greedy matchable graphs. In International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 1335 of LNCS, pages 184-198. Springer, 1997. Google Scholar
  27. G. Ducoffe. Optimal diameter computation within bounded clique-width graphs. Technical Report 2011.08448, arXiv, 2020. Google Scholar
  28. G. Ducoffe and A. Popa. The b-Matching Problem in Distance-Hereditary Graphs and Beyond. In 29th International Symposium on Algorithms and Computation (ISAAC 2018), volume 123 of Leibniz International Proceedings in Informatics (LIPIcs), pages 30:1-30:13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  29. G. Ducoffe and A. Popa. The use of a pruned modular decomposition for Maximum Matching algorithms on some graph classes. Discrete Applied Mathematics, 291:201-222, 2021. Google Scholar
  30. J. Edmonds. Paths, trees, and flowers. Canadian J. of mathematics, 17(3):449-467, 1965. Google Scholar
  31. Wolfgang Espelage, Frank Gurski, and Egon Wanke. How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. In International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 1 of LNCS, pages 117-128. Springer, 2001. URL: https://doi.org/10.1007/3-540-45477-2_12.
  32. T. Fluschnik, G.B. Mertzios, and A. Nichterlein. Kernelization lower bounds for finding constant-size subgraphs. In Conference on Computability in Europe, pages 183-193. Springer, 2018. Google Scholar
  33. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Intractability of clique-width parameterizations. SIAM Journal on Computing, 39(5):1941-1956, 2010. URL: https://doi.org/10.1137/080742270.
  34. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Almost optimal lower bounds for problems parameterized by clique-width. SIAM Journal on Computing, 43(5):1541-1563, 2014. URL: https://doi.org/10.1137/130910932.
  35. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Clique-width III: Hamiltonian Cycle and the Odd Case of Graph Coloring. ACM Transactions on Algorithms (TALG), 15(1):9, 2019. URL: https://doi.org/10.1145/3280824.
  36. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Michal Pilipczuk, and Marcin Wrochna. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. ACM Transactions on Algorithms (TALG), 14(3):34:1-34:45, 2018. URL: https://doi.org/10.1145/3186898.
  37. J.-L. Fouquet, V. Giakoumakis, and J.-M. Vanherpe. Bipartite graphs totally decomposable by canonical decomposition. International J. of Foundations of Computer Science, 10(04):513-533, 1999. Google Scholar
  38. J.-L. Fouquet, I. Parfenoff, and H. Thuillier. An O(n)-time algorithm for maximum matching in P₄-tidy graphs. Information processing letters, 62(6):281-287, 1997. Google Scholar
  39. Martin Fürer. A natural generalization of bounded tree-width and bounded clique-width. In Latin American Symposium on Theoretical Informatics, pages 72-83. Springer, 2014. Google Scholar
  40. H.N. Gabow. Data structures for weighted matching and extensions to b-matching and f-factors. ACM Transactions on Algorithms (TALG), 14(3):1-80, 2018. Google Scholar
  41. H.N. Gabow and P. Sankowski. Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors. SIAM Journal on Computing, 50(2):440-486, 2021. Google Scholar
  42. T. Gallai. Kritische graphen II. Magyar Tud. Akad. Mat. Kutato Int. Kozl., 8:373-395, 1963. Google Scholar
  43. T. Gallai. Maximale systeme unabhangiger kanten. Magyar Tud. Akad. Mat. Kutato Int. Kozl., 9:401-413, 1964. Google Scholar
  44. A. Gerards. Matching. Handbooks in operations research and management science, 7:135-224, 1995. Google Scholar
  45. Archontia C. Giannopoulou, George B. Mertzios, and Rolf Niedermeier. Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs. Theoretical Computer Science, 689:67-95, 2017. URL: https://doi.org/10.1016/j.tcs.2017.05.017.
  46. F. Glover. Maximum matching in a convex bipartite graph. Naval Research Logistics (NRL), 14(3):313-316, 1967. Google Scholar
  47. Martin Charles Golumbic and Udi Rotics. On the clique-width of some perfect graph classes. International Journal of Foundations of Computer Science, 11(03):423-443, 2000. URL: https://doi.org/10.1142/S0129054100000260.
  48. Torben Hagerup, Jyrki Katajainen, Naomi Nishimura, and Prabhakar Ragde. Characterizing multiterminal flow networks and computing flows in networks of small treewidth. Journal of Computer and System Sciences, 57(3):366-375, 1998. Google Scholar
  49. F. Hegerfeld and S. Kratsch. On Adaptive Algorithms for Maximum Matching. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132, pages 71:1-71:16. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  50. Yoichi Iwata, Tomoaki Ogasawara, and Naoto Ohsaka. On the power of tree-depth for fully polynomial FPT algorithms. In International Symposium on Theoretical Aspects of Computer Science (STACS), volume 96 of Leibniz International Proceedings in Informatics (LIPIcs), pages 41:1-41:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.41.
  51. S. Kratsch and F. Nelles. Efficient and Adaptive Parameterized Algorithms on Modular Decompositions. In European Symposium on Algorithms (ESA), pages 55:1-55:15, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.55.
  52. S. Kratsch and F. Nelles. Efficient Parameterized Algorithms for Computing All-Pairs Shortest Paths. In International Symposium on Theoretical Aspects of Computer Science (STACS), volume 154, pages 38:1-38:15. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  53. Y. T. Lee and A. Sidford. Path Finding I: Solving Linear Programs with$$1~ O (sqrt (rank)) Linear System Solves. Technical Report 1312.6677, arXiv, 2013. Google Scholar
  54. Y. Liang and C. Rhee. Finding a maximum matching in a circular-arc graph. Information processing letters, 45(4):185-190, 1993. Google Scholar
  55. L. Lovász and M. Plummer. Matching theory, volume 367. American Mathematical Soc., 2009. Google Scholar
  56. A. Madry. Navigating central path with electrical flows: From flows to matchings, and back. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 253-262. IEEE, 2013. Google Scholar
  57. Johann A. Makowsky and Udi Rotics. On the clique-width of graphs with few P₄’s. International Journal of Foundations of Computer Science, 10(03):329-348, 1999. URL: https://doi.org/10.1142/S0129054199000241.
  58. G. Mertzios, A. Nichterlein, and R. Niedermeier. A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs. SIAM Journal on Discrete Mathematics, 32(4):2820-2835, 2018. Google Scholar
  59. George B. Mertzios, André Nichterlein, and Rolf Niedermeier. The power of linear-time data reduction for maximum matching. In International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 83 of Leibniz International Proceedings in Informatics (LIPIcs), pages 46:1-46:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.MFCS.2017.46.
  60. 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
  61. A. Moitra and R. Johnson. A parallel algorithm for maximum matching on interval graphs. In ICPP, 1989. Google Scholar
  62. S. Oum and P. Seymour. Approximating clique-width and branch-width. Journal of Combinatorial Theory, Series B, 96(4):514-528, 2006. Google Scholar
  63. M.W. Padberg and M.R. Rao. The Russian method for linear inequalities III: Bounded integer programming. Technical Report 78, INRIA, 1981. Google Scholar
  64. W.R. Pulleyblank. Faces of Matching Polyhedra. PhD thesis, Univ. of Waterloo, Dept. Combinatorics and Optimization, 1973. Google Scholar
  65. Michaël Rao. Solving some NP-complete problems using split decomposition. Discrete Applied Mathematics, 156(14):2768-2780, 2008. URL: https://doi.org/10.1016/j.dam.2007.11.013.
  66. J. Renegar. A polynomial-time algorithm, based on Newton’s method, for linear programming. Mathematical programming, 40(1):59-93, 1988. Google Scholar
  67. J.W. Thatcher and J.B. Wright. Generalized finite automata theory with an application to a decision problem of second-order logic. Mathematical systems theory, 2(1):57-81, 1968. Google Scholar
  68. N. Trinajstić, D.J. Klein, and M. Randić. On some solved and unsolved problems of chemical graph theory. International Journal of Quantum Chemistry, 30(S20):699-742, 1986. Google Scholar
  69. W. Tutte. A short proof of the factor theorem for finite graphs. Canad. J. Math, 6(1954):347-352, 1954. Google Scholar
  70. W.T. Tutte. The factorization of linear graphs. Journal of the London Mathematical Society, 1(2):107-111, 1947. Google Scholar
  71. W.T. Tutte. Antisymmetrical digraphs. Canadian Journal of Mathematics, 19:1101-1117, 1967. Google Scholar
  72. V. Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the ICM, volume 3, pages 3431-3472. World Scientific, 2018. Google Scholar
  73. V. Vassilevska Williams and R.R. Williams. Subcubic equivalences between path, matrix, and triangle problems. Journal of the ACM (JACM), 65(5):1-38, 2018. Google Scholar
  74. 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
  75. R. Yuster. Maximum matching in regular and almost regular graphs. Algorithmica, 66(1):87-92, 2013. Google Scholar
  76. R. Yuster and U. Zwick. Maximum matching in graphs with an excluded minor. In Proceedings of the eighteenth annual ACM-SIAM Symposium on Discrete Algorithms, pages 108-117. Society for Industrial and Applied Mathematics, 2007. 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