Document Open Access Logo

Efficient and Adaptive Parameterized Algorithms on Modular Decompositions

Authors Stefan Kratsch, Florian Nelles

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.55.pdf
  • Filesize: 0.5 MB
  • 15 pages

Document Identifiers

Author Details

Stefan Kratsch
  • Department of Computer Science, Humboldt-Universität zu Berlin, Germany
Florian Nelles
  • Department of Computer Science, Humboldt-Universität zu Berlin, Germany

Cite As Get BibTex

Stefan Kratsch and Florian Nelles. Efficient and Adaptive Parameterized Algorithms on Modular Decompositions. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.55

Abstract

We study the influence of a graph parameter called modular-width on the time complexity for optimally solving well-known polynomial problems such as Maximum Matching, Triangle Counting, and Maximum s-t Vertex-Capacitated Flow. The modular-width of a graph depends on its (unique) modular decomposition tree, and can be computed in linear time O(n+m) for graphs with n vertices and m edges. Modular decompositions are an important tool for graph algorithms, e.g., for linear-time recognition of certain graph classes.
Throughout, we obtain efficient parameterized algorithms of running times O(f(mw)n+m), O(n+f(mw)m) , or O(f(mw)+n+m) for low polynomial functions f and graphs of modular-width mw. Our algorithm for Maximum Matching, running in time O(mw^2 log mw n+m), is both faster and simpler than the recent O(mw^4n+m) time algorithm of Coudert et al. (SODA 2018). For several other problems, e.g., Triangle Counting and Maximum b-Matching, we give adaptive algorithms, meaning that their running times match the best unparameterized algorithms for worst-case modular-width of mw=Theta(n) and they outperform them already for mw=o(n), until reaching linear time for mw=O(1).

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • efficient parameterized algorithms
  • modular-width
  • adaptive algorithms

Metrics

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

Related Versions

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for LCS and other sequence similarity measures. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 59-78, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.14.
  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. Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-223, 1997. URL: http://dx.doi.org/10.1007/BF02523189.
  4. Matthias Bentert, Till Fluschnik, André Nichterlein, and Rolf Niedermeier. Parameterized aspects of triangle enumeration. In Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Bordeaux, France, September 11-13, 2017, Proceedings, pages 96-110, 2017. URL: http://dx.doi.org/10.1007/978-3-662-55751-8_9.
  5. 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.
  6. Karl Bringmann and Marvin Künnemann. Quadratic conditional lower bounds for string problems and dynamic time warping. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 79-97, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.15.
  7. Karl Bringmann and Marvin Künnemann. Multivariate fine-grained complexity of longest common subsequence. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1216-1235, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.79.
  8. 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, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2765-2784, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.176.
  9. Alain Cournier and Michel Habib. A new linear algorithm for modular decomposition. In Sophie Tison, editor, Trees in Algebra and Programming - CAAP'94, 19th International Colloquium, Edinburgh, U.K., April 11-13, 1994, Proceedings, volume 787 of Lecture Notes in Computer Science, pages 68-84. Springer, 1994. URL: http://dx.doi.org/10.1007/BFb0017474.
  10. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  11. Jack Edmonds. Paths, trees, and flowers. Canadian Journal of mathematics, 17(3):449-467, 1965. Google Scholar
  12. 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.
  13. Till Fluschnik, Christian Komusiewicz, George B. Mertzios, André Nichterlein, Rolf Niedermeier, and Nimrod Talmon. When can graph hyperbolicity be computed in linear time? In Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John’s, NL, Canada, July 31 - August 2, 2017, Proceedings, pages 397-408, 2017. URL: http://dx.doi.org/10.1007/978-3-319-62127-2_34.
  14. Fedor V Fomin, Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh, and Marcin Wrochna. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1419-1432. Society for Industrial and Applied Mathematics, 2017. Google Scholar
  15. Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. J. Comput. Syst. Sci., 50(2):259-273, 1995. URL: http://dx.doi.org/10.1006/jcss.1995.1022.
  16. Harold N. Gabow. Data structures for weighted matching and extensions to dollarbdollar-matching and dollarfdollar-factors. CoRR, abs/1611.07541, 2016. URL: http://arxiv.org/abs/1611.07541.
  17. François Le Gall. Powers of tensors and fast matrix multiplication. In Katsusuke Nabeshima, Kosaku Nagasaka, Franz Winkler, and Ágnes Szántó, editors, International Symposium on Symbolic and Algebraic Computation, ISSAC '14, Kobe, Japan, July 23-25, 2014, pages 296-303. ACM, 2014. URL: http://dl.acm.org/citation.cfm?id=2608628, URL: http://dx.doi.org/10.1145/2608628.2608664.
  18. Tibor Gallai. Transitiv orientierbare graphen. Acta Mathematica Hungarica, 18(1-2):25-66, 1967. Google Scholar
  19. Archontia C. Giannopoulou, George B. Mertzios, and Rolf Niedermeier. Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs. CoRR, abs/1506.01652, 2015. URL: http://arxiv.org/abs/1506.01652.
  20. Andrew V. Goldberg and Satish Rao. Flows in undirected unit capacity networks. SIAM J. Discrete Math., 12(1):1-5, 1999. URL: http://dx.doi.org/10.1137/S089548019733103X.
  21. Michel Habib and Christophe Paul. A survey of the algorithmic aspects of modular decomposition. Computer Science Review, 4(1):41-59, 2010. URL: http://dx.doi.org/10.1016/j.cosrev.2010.01.001.
  22. Jianxiu Hao and James B. Orlin. A faster algorithm for finding the minimum cut in a directed graph. J. Algorithms, 17(3):424-446, 1994. URL: http://dx.doi.org/10.1006/jagm.1994.1043.
  23. 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, August 24-26, 2016, Aarhus, Denmark, volume 63 of LIPIcs, pages 16:1-16:11. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2016.16.
  24. Yoichi Iwata, Tomoaki Ogasawara, and Naoto Ohsaka. On the power of tree-depth for fully polynomial FPT algorithms. In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, pages 41:1-41:14, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2018.41.
  25. David R. Karger. Minimum cuts in near-linear time. J. ACM, 47(1):46-76, 2000. URL: http://dx.doi.org/10.1145/331605.331608.
  26. Stefan Kratsch and Florian Nelles. Efficient and adaptive parameterized algorithms on modular decompositions. CoRR, abs/1804.10173, 2018. URL: http://arxiv.org/abs/1804.10173.
  27. Ross M McConnell and Jeremy P Spinrad. Linear-time modular decomposition and efficient transitive orientation of comparability graphs. In Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, pages 536-545. Society for Industrial and Applied Mathematics, 1994. Google Scholar
  28. George B. Mertzios, André Nichterlein, and Rolf Niedermeier. Fine-grained algorithm design for matching. CoRR, abs/1609.08879, 2016. URL: http://arxiv.org/abs/1609.08879.
  29. Silvio Micali and Vijay V. Vazirani. An o(sqrt(|v|) |e|) algorithm for finding maximum matching in general graphs. In 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13-15 October 1980, pages 17-27. IEEE Computer Society, 1980. URL: http://dx.doi.org/10.1109/SFCS.1980.12.
  30. James B. Orlin. Max flows in o(nm) time, or better. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 765-774, 2013. URL: http://dx.doi.org/10.1145/2488608.2488705.
  31. 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.
  32. Thomas Schank and Dorothea Wagner. Finding, counting and listing all triangles in large graphs, an experimental study. In Experimental and Efficient Algorithms, 4th InternationalWorkshop, WEA 2005, Santorini Island, Greece, May 10-13, 2005, Proceedings, pages 606-609, 2005. URL: http://dx.doi.org/10.1007/11427186_54.
  33. Mechthild Stoer and Frank Wagner. A simple min-cut algorithm. J. ACM, 44(4):585-591, 1997. URL: http://dx.doi.org/10.1145/263867.263872.
  34. Marc Tedder, Derek G. Corneil, Michel Habib, and Christophe Paul. Simpler linear-time modular decomposition via recursive factorizing permutations. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, volume 5125 of Lecture Notes in Computer Science, pages 634-645. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-70575-8_52.
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