Document Open Access Logo

On Adaptive Algorithms for Maximum Matching

Authors Falko Hegerfeld, Stefan Kratsch

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.71.pdf
  • Filesize: 0.59 MB
  • 16 pages

Document Identifiers

Author Details

Falko Hegerfeld
  • Humboldt-Universität zu Berlin, Germany
Stefan Kratsch
  • Humboldt-Universität zu Berlin, Germany

Cite AsGet BibTex

Falko Hegerfeld and Stefan Kratsch. On Adaptive Algorithms for Maximum Matching. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 71:1-71:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.71

Abstract

In the fundamental Maximum Matching problem the task is to find a maximum cardinality set of pairwise disjoint edges in a given undirected graph. The fastest algorithm for this problem, due to Micali and Vazirani, runs in time O(sqrt{n}m) and stands unbeaten since 1980. It is complemented by faster, often linear-time, algorithms for various special graph classes. Moreover, there are fast parameterized algorithms, e.g., time O(km log n) relative to tree-width k, which outperform O(sqrt{n}m) when the parameter is sufficiently small. We show that the Micali-Vazirani algorithm, and in fact any algorithm following the phase framework of Hopcroft and Karp, is adaptive to beneficial input structure. We exhibit several graph classes for which such algorithms run in linear time O(n+m). More strongly, we show that they run in time O(sqrt{k}m) for graphs that are k vertex deletions away from any of several such classes, without explicitly computing an optimal or approximate deletion set; before, most such bounds were at least Omega(km). Thus, any phase-based matching algorithm with linear-time phases obliviously interpolates between linear time for k=O(1) and the worst case of O(sqrt{n}m) when k=Theta(n). We complement our findings by proving that the phase framework by itself still allows Omega(sqrt{n}) phases, and hence time Omega(sqrt{n}m), even on paths, cographs, and bipartite chain graphs.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Matchings and factors
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Matchings
  • Adaptive Analysis
  • Parameterized Complexity

Metrics

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

Related Versions

References

  1. Amir Abboud, Virginia Vassilevska Williams, and Joshua Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete Algorithms, pages 377-391. SIAM, 2016. Google Scholar
  2. Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching Triangles and Basing Hardness on an Extremely Popular Conjecture. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 41-50. ACM, 2015. URL: http://dx.doi.org/10.1145/2746539.2746594.
  3. Jérémy Barbay, Johannes Fischer, and Gonzalo Navarro. LRM-Trees: Compressed indices, adaptive sorting, and compressed permutations. Theor. Comput. Sci., 459:26-41, 2012. URL: http://dx.doi.org/10.1016/j.tcs.2012.08.010.
  4. Jérémy Barbay and Gonzalo Navarro. On compressing permutations and adaptive sorting. Theor. Comput. Sci., 513:109-123, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2013.10.019.
  5. Holger Bast, Kurt Mehlhorn, Guido Schafer, and Hisao Tamaki. Matching algorithms are fast in sparse random graphs. Theory of Computing Systems, 39(1):3-14, 2006. Google Scholar
  6. Matthias Bentert, Till Fluschnik, André Nichterlein, and Rolf Niedermeier. Parameterized aspects of triangle enumeration. In International Symposium on Fundamentals of Computation Theory, pages 96-110. Springer, 2017. Google Scholar
  7. Claude Berge. Two theorems in graph theory. Proceedings of the National Academy of Sciences, 43(9):842-844, 1957. Google Scholar
  8. Norbert Blum. A new approach to maximum matching in general graphs. In International Colloquium on Automata, Languages, and Programming, pages 586-597. Springer, 1990. Google Scholar
  9. Karl Bringmann. Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 661-670. IEEE Computer Society, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.76.
  10. Maw-Shang Chang. Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs. In International Symposium on Algorithms and Computation, pages 146-155. Springer, 1996. Google Scholar
  11. David Coudert, Guillaume Ducoffe, and Alexandru Popa. Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2765-2784. Society for Industrial and Applied Mathematics, 2018. Google Scholar
  12. Elias Dahlhaus and Marek Karpinski. Matching and multidimensional matching in chordal and strongly chordal graphs. Discrete Applied Mathematics, 84(1-3):79-91, 1998. Google Scholar
  13. Yann Disser and Stefan Kratsch. Robust and Adaptive Search. In Heribert Vollmer and Brigitte Vallée, editors, 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, volume 66 of LIPIcs, pages 26:1-26:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2017.26.
  14. Feodor F. Dragan. On greedy matching ordering and greedy matchable graphs. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 184-198. Springer, 1997. Google Scholar
  15. Guillaume Ducoffe and Alexandru Popa. A quasi linear-time b-Matching algorithm on distance-hereditary graphs and bounded split-width graphs. arXiv preprint, 2018. URL: http://arxiv.org/abs/1804.09393.
  16. Guillaume Ducoffe and Alexandru Popa. The use of a pruned modular decomposition for Maximum Matching algorithms on some graph classes. In 29th International Symposium on Algorithms and Computation (ISAAC 2018), 29th International Symposium on Algorithms and Computation (ISAAC 2018), Jiaoxi, Yilan County, Taiwan, December 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ISAAC.2018.144.
  17. Jack Edmonds. Paths, Trees, and Flowers. Canadian Journal of Mathematics, 17:449–467, 1965. URL: http://dx.doi.org/10.4153/CJM-1965-045-4.
  18. Vladimir Estivill-Castro and Derick Wood. A Survey of Adaptive Sorting Algorithms. ACM Comput. Surv., 24(4):441-476, 1992. URL: http://dx.doi.org/10.1145/146370.146381.
  19. Till Fluschnik, Christian Komusiewicz, George B Mertzios, André Nichterlein, Rolf Niedermeier, and Nimrod Talmon. When can graph hyperbolicity be computed in linear time? In Workshop on Algorithms and Data Structures, pages 397-408. Springer, 2017. Google Scholar
  20. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Michał Pilipczuk, and Marcin Wrochna. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. ACM Transactions on Algorithms (TALG), 14(3):34, 2018. Google Scholar
  21. Jean-Luc Fouquet, Vassilis Giakoumakis, and Jean-Marie Vanherpe. Bipartite graphs totally decomposable by canonical decomposition. International Journal of Foundations of Computer Science, 10(04):513-533, 1999. Google Scholar
  22. Jean-Luc Fouquet, Igor Parfenoff, and Henri Thuillier. An 𝒪(n) time algorithm for maximum matching in P₄-tidy graphs. Information Processing Letters, 62(6):281-287, 1997. Google Scholar
  23. Harold N. Gabow and Robert E. Tarjan. Faster scaling algorithms for general graph matching problems. Journal of the ACM (JACM), 38(4):815-853, 1991. Google Scholar
  24. Frédéric Gardi. Efficient algorithms for disjoint matchings among intervals and related problems. In Discrete Mathematics and Theoretical Computer Science, pages 168-180. Springer, 2003. Google Scholar
  25. 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. Google Scholar
  26. Fred Glover. Maximum matching in a convex bipartite graph. Naval Research Logistics Quarterly, 14(3):313-316, 1967. Google Scholar
  27. Andrew V. Goldberg and Alexander V. Karzanov. Maximum skew-symmetric flows and matchings. Mathematical Programming, 100(3):537-568, 2004. Google Scholar
  28. Jiong Guo, Christian Komusiewicz, Rolf Niedermeier, and Johannes Uhlmann. A more relaxed model for graph-based data clustering: s-plex editing. In International Conference on Algorithmic Applications in Management, pages 226-239. Springer, 2009. Google Scholar
  29. John E. Hopcroft and Richard M. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing, 2(4):225-231, 1973. Google Scholar
  30. Thore Husfeldt. Computing Graph Distances Parameterized by Treewidth and Diameter. In Jiong Guo and Danny Hermelin, editors, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016), volume 63 of Leibniz International Proceedings in Informatics (LIPIcs), pages 16:1-16:11, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2016.16.
  31. Yoichi Iwata, Tomoaki Ogasawara, and Naoto Ohsaka. On the Power of Tree-Depth for Fully Polynomial FPT Algorithms. In LIPIcs-Leibniz International Proceedings in Informatics, volume 96. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  32. Leon Kellerhals. Parameterized Algorithms for Network Flows. Master’s thesis, TU Berlin, 2018. URL: https://fpt.akt.tu-berlin.de/publications/thesis/MA-leon-kellerhals.pdf.
  33. Stefan Kratsch and Florian Nelles. Efficient and Adaptive Parameterized Algorithms on Modular Decompositions. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms (ESA 2018), volume 112 of Leibniz International Proceedings in Informatics (LIPIcs), pages 55:1-55:15, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2018.55.
  34. Y. Daniel Liang and Chongkye Rhee. Finding a maximum matching in a circular-arc graph. Information Processing Letters, 45(4):185-190, 1993. Google Scholar
  35. Aleksander Madry. Navigating central path with electrical flows: From flows to matchings, and back. In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pages 253-262. IEEE, 2013. Google Scholar
  36. George B. Mertzios, André Nichterlein, and Rolf Niedermeier. Fine-grained algorithm design for matching. Technical report, Technical Report, 2016. Google Scholar
  37. George B. Mertzios, André Nichterlein, and Rolf Niedermeier. The Power of Linear-Time Data Reduction for Maximum Matching. In Kim G. Larsen, Hans L. Bodlaender, and Jean-Francois Raskin, editors, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), volume 83 of Leibniz International Proceedings in Informatics (LIPIcs), pages 46:1-46:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2017.46.
  38. George B. Mertzios, André Nichterlein, and Rolf Niedermeier. A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs. SIAM Journal on Discrete Mathematics, 32(4):2820-2835, 2018. Google Scholar
  39. Silvio Micali and Vijay V. Vazirani. An O(√|V| |E|) algorithm for finding maximum matching in general graphs. In 21st Annual Symposium on Foundations of Computer Science, 1980, pages 17-27. IEEE, 1980. Google Scholar
  40. J. Nešetřil and P. Ossona de Mendez. Sparsity (Graphs, Structures, and Algorithms), volume 28 of Algorithms and Combinatorics. Springer, 2012. Google Scholar
  41. Mihai Patrascu and Ryan Williams. On the Possibility of Faster SAT Algorithms. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1065-1075. SIAM, 2010. URL: http://dx.doi.org/10.1137/1.9781611973075.86.
  42. Stephen B. Seidman and Brian L. Foster. A graph-theoretic generalization of the clique concept. Journal of Mathematical sociology, 6(1):139-154, 1978. Google Scholar
  43. George Steiner and Julian S Yeomans. A linear time algorithm for maximum matchings in convex, bipartite graphs. Computers &Mathematics with Applications, 31(12):91-96, 1996. Google Scholar
  44. René Van Bevern, Hannes Moser, and Rolf Niedermeier. Approximation and tidying—a problem kernel for s-plex cluster vertex deletion. Algorithmica, 62(3-4):930-950, 2012. Google Scholar
  45. Ming-Shing Yu and Cheng-Hsing Yang. An 𝒪(n) time algorithm for maximum matching on cographs. Information Processing Letters, 47(2):89-93, 1993. Google Scholar
  46. Raphael Yuster. Maximum matching in regular and almost regular graphs. Algorithmica, 66(1):87-92, 2013. Google Scholar
  47. Raphael Yuster and Uri 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 Imprint Privacy Contact