Document Open Access Logo

Fully Polynomial-Time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication

Authors Matthias Bentert, Klaus Heeger, Tomohiro Koana

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.16.pdf
  • Filesize: 0.7 MB
  • 16 pages

Document Identifiers

Author Details

Matthias Bentert
  • University of Bergen, Norway
Klaus Heeger
  • Algorithmics and Computational Complexity, Technische Universität Berlin, Germany
Tomohiro Koana
  • Algorithmics and Computational Complexity, Technische Universität Berlin, Germany

Funding

  • Bentert, Matthias: Supported by the European Research Council (ERC) project LOPRE (819416) under the Horizon 2020 research and innovation program.
  • Heeger, Klaus: Supported by Deutsche Forschungsgemeinschaft (DFG) project NI 369/16.
  • Koana, Tomohiro: Supported by the DFG project DiPa (NI 369/21).

Acknowledgements

We thank Vincent Borko for fruitful discussions regarding the results for finding small induced subgraphs and anonymous reviewers for their constructive feedback which, in particular, helped improving the running time of our algorithm for All-Pairs Shortest Paths.

Cite AsGet BibTex

Matthias Bentert, Klaus Heeger, and Tomohiro Koana. Fully Polynomial-Time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.16

Abstract

We study the computational complexity of several polynomial-time-solvable graph problems parameterized by vertex integrity, a measure of a graph’s vulnerability to vertex removal in terms of connectivity. Vertex integrity is the smallest number ι such that there is a set S of ι' ≤ ι vertices such that every connected component of G-S contains at most ι-ι' vertices. It is known that the vertex integrity lies between the well-studied parameters vertex cover number and tree-depth. Our work follows similar studies for vertex cover number [Alon and Yuster, ESA 2007] and tree-depth [Iwata, Ogasawara, and Ohsaka, STACS 2018]. Alon and Yuster designed algorithms for graphs with small vertex cover number using fast matrix multiplications. We demonstrate that fast matrix multiplication can also be effectively used when parameterizing by vertex integrity ι by developing efficient algorithms for problems including an O(ι^{ω-1}n)-time algorithm for Maximum Matching and an O(ι^{(ω-1)/2}n²) ⊆ O(ι^{0.687} n²)-time algorithm for All-Pairs Shortest Paths. These algorithms can be faster than previous algorithms parameterized by tree-depth, for which fast matrix multiplication is not known to be effective.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Mathematics of computing → Matchings and factors
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Shortest paths
Keywords
  • FPT in P
  • Algebraic Algorithms
  • Adaptive Algorithms
  • Subgraph Detection
  • Matching
  • APSP

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 Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '16), pages 377-391. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch28.
  2. Noga Alon and Raphael Yuster. Fast algorithms for maximum subset matching and all-pairs shortest paths in graphs with a (not so) small vertex cover. In Proceedings of the 15th Annual European Symposium on Algorithms (ESA '07), pages 175-186, 2007. URL: https://doi.org/10.1007/978-3-540-75520-3_17.
  3. Curtis A Barefoot, Roger Entringer, and Henda Swart. Vulnerability in graphs - A comparative survey. Journal of Combinatorial Mathematics and Combinatorial Computing, 1(38):13-22, 1987. Google Scholar
  4. D. Benko, C. Ernst, and Dominic Lanphier. Asymptotic bounds on the integrity of graphs and separator theorems for graphs. SIAM Journal on Discrete Mathematics, 23(1):265-277, 2009. URL: https://doi.org/10.1137/070692698.
  5. Matthias Bentert, Till Fluschnik, André Nichterlein, and Rolf Niedermeier. Parameterized aspects of triangle enumeration. Journal of Computer and System Sciences, 103:61-77, 2019. URL: https://doi.org/10.1016/j.jcss.2019.02.004.
  6. Hans L. Bodlaender, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, and Tom C. van der Zanden. Subgraph isomorphism on graph classes that exclude a substructure. Algorithmica, 82(12):3566-3587, 2020. URL: https://doi.org/10.1007/s00453-020-00737-z.
  7. Karl Bringmann, Thore Husfeldt, and Måns Magnusson. Multivariate analysis of orthogonal range searching and graph distances. Algorithmica, 82(8):2292-2315, 2020. URL: https://doi.org/10.1007/s00453-020-00680-z.
  8. James R. Bunch and John E. Hopcroft. Triangular factorization and inversion by fast matrix multiplication. Mathematics of Computation, 28(125):231-236, 1974. URL: https://doi.org/10.1090/S0025-5718-1974-0331751-8.
  9. Peter Bürgisser, Michael Clausen, and Mohammad Amin Shokrollahi. Algebraic complexity theory. Springer, 1997. URL: https://doi.org/0.1007/978-3-662-03338-8.
  10. Shucheng Chi, Ran Duan, Tianle Xie, and Tianyi Zhang. Faster min-plus product for monotone instances. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC '22), pages 1529-1542. ACM, 2022. URL: https://doi.org/10.1145/3519935.3520057.
  11. Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM Journal on Computing, 14(1):210-223, 1985. URL: https://doi.org/10.1137/0214017.
  12. Derek G. Corneil, Yehoshua Perl, and Lorna K. Stewart. A linear recognition algorithm for cographs. SIAM Journal on Computing, 14(4):926-934, 1985. URL: https://doi.org/10.1137/0214065.
  13. David Coudert, Guillaume Ducoffe, and Alexandru Popa. Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. ACM Transactions on Algorithms, 15(3):33:1-33:57, 2019. URL: https://doi.org/10.1145/3310228.
  14. Mingyang Deng, Yael Kirkpatrick, Victor Rong, Virginia Vassilevska Williams, and Ziqian Zhong. New additive approximations for shortest paths and cycles. In Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP '22), pages 50:1-50:10. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.ICALP.2022.50.
  15. Pål Grønås Drange, Markus S. Dregi, and Pim van 't Hof. On the computational complexity of vertex integrity and component order connectivity. Algorithmica, 76(4):1181-1202, 2016. URL: https://doi.org/10.1007/s00453-016-0127-x.
  16. Pavel Dvorák, Eduard Eiben, Robert Ganian, Dusan Knop, and Sebastian Ordyniak. The complexity landscape of decompositional parameters for ILP: Programs with few global variables and constraints. Artificial Intelligence, 300:103561, 2021. URL: https://doi.org/10.1016/j.artint.2021.103561.
  17. Pavlos Eirinakis, Matthew D. Williamson, and K. Subramani. On the Shoshan-Zwick algorithm for the all-pairs shortest path problem. Journal of Graph Algorithms and Applications, 21(2):177-181, 2017. URL: https://doi.org/10.7155/jgaa.00410.
  18. Friedrich Eisenbrand and Fabrizio Grandoni. On the complexity of fixed parameter clique and dominating set. Theoretical Computer Science, 326(1-3):57-67, 2004. URL: https://doi.org/10.1016/j.tcs.2004.05.009.
  19. Michael J. Fischer and Albert R. Meyer. Boolean matrix multiplication and transitive closure. In Proceedings of the 12th Annual Symposium on Switching and Automata Theory (SWAT '71), pages 129-131. IEEE Computer Society, 1971. URL: https://doi.org/10.1109/SWAT.1971.4.
  20. 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, 14(3):34:1-34:45, 2018. URL: https://doi.org/10.1145/3186898.
  21. François Le Gall. Faster algorithms for rectangular matrix multiplication. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS '12), pages 514-523. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/FOCS.2012.80.
  22. Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, and Yota Otachi. Exploring the gap between treedepth and vertex cover through vertex integrity. Theor. Comput. Sci., 918:60-76, 2022. URL: https://doi.org/10.1016/j.tcs.2022.03.021.
  23. Chris D. Godsil. Algebraic combinatorics. Chapman and Hall, 1993. Google Scholar
  24. Nicholas J. A. Harvey. Algebraic algorithms for matching and matroid problems. SIAM Journal on Computing, 39(2):679-702, 2009. URL: https://doi.org/10.1137/070684008.
  25. Falko Hegerfeld and Stefan Kratsch. On adaptive algorithms for maximum matching. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP '19), pages 71:1-71:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.71.
  26. Yoichi Iwata, Tomoaki Ogasawara, and Naoto Ohsaka. On the power of tree-depth for fully polynomial FPT algorithms. In Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science (STACS '18), pages 41:1-41:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.41.
  27. Stefan Kratsch and Florian Nelles. Efficient parameterized algorithms for computing all-pairs shortest paths. In Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS '20), pages 38:1-38:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.38.
  28. Michael Lampis and Valia Mitsou. Fine-grained meta-theorems for vertex integrity. In Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC '21), pages 34:1-34:15, 2021. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2021.34.
  29. Euiwoong Lee. Partitioning a graph into small pieces with applications to path transversal. Mathematical Programming, 177(1-2):1-19, 2019. URL: https://doi.org/10.1007/s10107-018-1255-7.
  30. László Lovász. On determinants, matchings, and random algorithms. In Proceedings of the 2nd International Symposium on Fundamentals of Computation Theory (FCT '79), pages 565-574. Akademie-Verlag, Berlin, 1979. Google Scholar
  31. Marcin Mucha and Piotr Sankowski. Maximum matchings via gaussian elimination. In Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS '04), pages 248-255, 2004. URL: https://doi.org/10.1109/FOCS.2004.40.
  32. Kazuo Murota. Matrices and matroids for systems analysis. Springer Science & Business Media, 1999. URL: https://doi.org/10.1007/978-3-642-03994-2.
  33. Jacob T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701-717, 1980. URL: https://doi.org/10.1145/322217.322225.
  34. Raimund Seidel. On the all-pairs-shortest-path problem. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC '92), pages 745-749. ACM, 1992. URL: https://doi.org/10.1145/129712.129784.
  35. Avi Shoshan and Uri Zwick. All pairs shortest paths in undirected graphs with integer weights. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS '99), pages 605-615, 1999. URL: https://doi.org/10.1109/SFFCS.1999.814635.
  36. William T. Tutte. The factorization of linear graphs. Journal of the London Mathematical Society, 1(2):107-111, 1947. URL: https://doi.org/10.1112/jlms/s1-22.2.107.
  37. Richard Ryan Williams. Faster all-pairs shortest paths via circuit complexity. SIAM Journal on Computing, 47(5):1965-1985, 2018. URL: https://doi.org/10.1137/15M1024524.
  38. Virginia Vassilevska Williams, Joshua R. Wang, Richard Ryan Williams, and Huacheng Yu. Finding four-node subgraphs in triangle time. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '15), pages 1671-1680, 2015. URL: https://doi.org/10.1137/1.9781611973730.111.
  39. Richard Zippel. Probabilistic algorithms for sparse polynomials. In Proceedings of the 2nd International Symposium on Symbolic and Algebraic Manipulation (EUROSM '79), pages 216-226. Springer, 1979. URL: https://doi.org/10.1007/3-540-09519-5_73.
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