Document Open Access Logo

Blazing a Trail via Matrix Multiplications: A Faster Algorithm for Non-Shortest Induced Paths

Authors Yung-Chung Chiu, Hsueh-I Lu

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.23.pdf
  • Filesize: 0.85 MB
  • 16 pages

Document Identifiers

Author Details

Yung-Chung Chiu
  • Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan
Hsueh-I Lu
  • Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan

Funding

  • Lu, Hsueh-I: MOST grants 110-2221-E-002-075-MY3 and 107-2221-E-002-032-MY3.

Cite AsGet BibTex

Yung-Chung Chiu and Hsueh-I Lu. Blazing a Trail via Matrix Multiplications: A Faster Algorithm for Non-Shortest Induced Paths. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.STACS.2022.23

Abstract

For vertices u and v of an n-vertex graph G, a uv-trail of G is an induced uv-path of G that is not a shortest uv-path of G. Berger, Seymour, and Spirkl [Discrete Mathematics 2021] gave the previously only known polynomial-time algorithm, running in O(n^{18}) time, to either output a uv-trail of G or ensure that G admits no uv-trail. We reduce the complexity to the time required to perform a poly-logarithmic number of multiplications of n²× n² Boolean matrices, leading to a largely improved O(n^{4.75})-time algorithm.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Induced subgraph
  • induced path
  • non-shortest path
  • dynamic data structure

Metrics

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

References

  1. Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Pawel Rzazewski, and Paul D. Seymour. Induced subgraphs of bounded treewidth and the container method. In Dániel Marx, editor, Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1948-1964, 2021. URL: https://doi.org/10.1137/1.9781611976465.116.
  2. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Dániel Marx, editor, Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 522-539, 2021. URL: https://doi.org/10.1137/1.9781611976465.32.
  3. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM, 42(4):844-856, 1995. URL: https://doi.org/10.1145/210332.210337.
  4. Claude Berge. Les problèmes de coloration en théorie des graphes. Publications de l'Institut de statistique de l'Université de Paris, 9:123-160, 1960. Google Scholar
  5. Claude Berge. Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind (Zusammenfassung). Wissenschaftliche Zeitschrift, Martin Luther Universität Halle-Wittenberg, Mathematisch-Naturwissenschaftliche Reihe, 10:114-115, 1961. Google Scholar
  6. Claude Berge. Graphs. North-Holland, Amsterdam, New York, 1985. Google Scholar
  7. Eli Berger, Paul D. Seymour, and Sophie Spirkl. Finding an induced path that is not a shortest path. Discrete Mathematics, 344(7):112398.1-112398.6, 2021. URL: https://doi.org/10.1016/j.disc.2021.112398.
  8. Daniel Bienstock. On the complexity of testing for odd holes and induced odd paths. Discrete Mathematics, 90(1):85-92, 1991. See [Daniel Bienstock, 1992] for corrigendum. URL: https://doi.org/10.1016/0012-365X(91)90098-M.
  9. Daniel Bienstock. Corrigendum to: D. Bienstock, "On the complexity of testing for odd holes and induced odd paths" Discrete Mathematics 90 (1991) 85-92. Discrete Mathematics, 102(1):109, 1992. URL: https://doi.org/10.1016/0012-365X(92)90357-L.
  10. Hsien-Chih Chang and Hsueh-I Lu. A faster algorithm to recognize even-hole-free graphs. Journal of Combinatorial Theory, Series B, 113:141-161, 2015. URL: https://doi.org/10.1016/j.jctb.2015.02.001.
  11. Yijia Chen and Jörg Flum. On parameterized path and chordless path problems. In Proceedings of the 22nd Annual IEEE Conference on Computational Complexity, pages 250-263, 2007. URL: https://doi.org/10.1109/CCC.2007.21.
  12. Hou-Teng Cheong and Hsueh-I Lu. Finding a shortest even hole in polynomial time. Journal of Graph Theory, 2022, to appear. URL: https://doi.org/10.1002/jgt.22748.
  13. Maria Chudnovsky, Gérard Cornuéjols, Xinming Liu, Paul D. Seymour, and Kristina Vušković. Recognizing Berge graphs. Combinatorica, 25(2):143-186, 2005. URL: https://doi.org/10.1007/s00493-005-0012-8.
  14. Maria Chudnovsky, Ken-ichi Kawarabayashi, and Paul Seymour. Detecting even holes. Journal of Graph Theory, 48(2):85-111, 2005. URL: https://doi.org/10.1002/jgt.20040.
  15. Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, and Stéphan Thomassé. On the maximum weight independent set problem in graphs without induced cycles of length at least five. SIAM Journal on Discrete Mathematics, 34(2):1472-1483, 2020. URL: https://doi.org/10.1137/19M1249473.
  16. Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas. The strong perfect graph theorem. Annals of Mathematics, 164(1):51-229, 2006. URL: https://doi.org/10.4007/annals.2006.164.51.
  17. Maria Chudnovsky, Alex Scott, and Paul Seymour. Detecting a long odd hole. Combinatorica, 41(1):1-30, 2021. URL: https://doi.org/10.1007/s00493-020-4301-z.
  18. Maria Chudnovsky, Alex Scott, and Paul Seymour. Finding a shortest odd hole. ACM Transactions on Algorithms, 17(2):13.1-13.21, 2021. URL: https://doi.org/10.1145/3447869.
  19. Maria Chudnovsky, Alex Scott, Paul Seymour, and Sophie Spirkl. Detecting an odd hole. Journal of the ACM, 67(1):5.1-5.12, 2020. URL: https://doi.org/10.1145/3375720.
  20. Maria Chudnovsky and Paul Seymour. The three-in-a-tree problem. Combinatorica, 30(4):387-417, 2010. URL: https://doi.org/10.1007/s00493-010-2334-4.
  21. Maria Chudnovsky and Paul D. Seymour. Even pairs in Berge graphs. Journal of Combinatorial Theory, Series B, 99(2):370-377, 2009. URL: https://doi.org/10.1016/j.jctb.2008.08.002.
  22. Maria Chudnovsky and Vaidy Sivaraman. Odd holes in bull-free graphs. SIAM Journal on Discrete Mathematics, 32(2):951-955, 2018. URL: https://doi.org/10.1137/17M1131301.
  23. Michele Conforti, Gérard Cornuéjols, Ajai Kapoor, and Kristina Vušković. Finding an even hole in a graph. In Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, pages 480-485, 1997. URL: https://doi.org/10.1109/SFCS.1997.646136.
  24. Michele Conforti, Gérard Cornuéjols, Ajai Kapoor, and Kristina Vušković. Even and odd holes in cap-free graphs. Journal of Graph Theory, 30(4):289-308, 1999. URL: https://doi.org/10.1002/(SICI)1097-0118(199904)30:4%3C289::AID-JGT4%3E3.0.CO;2-3.
  25. Michele Conforti, Gérard Cornuéjols, Ajai Kapoor, and Kristina Vušković. Even-hole-free graphs Part I: Decomposition theorem. Journal of Graph Theory, 39(1):6-49, 2002. URL: https://doi.org/10.1002/jgt.10006.
  26. Michele Conforti, Gérard Cornuéjols, Ajai Kapoor, and Kristina Vušković. Even-hole-free graphs Part II: Recognition algorithm. Journal of Graph Theory, 40(4):238-266, 2002. URL: https://doi.org/10.1002/jgt.10045.
  27. Michele Conforti, Gérard Cornuéjols, Xinming Liu, Kristina Vušković, and Giacomo Zambelli. Odd hole recognition in graphs of bounded clique size. SIAM Journal on Discrete Mathematics, 20(1):42-48, 2006. URL: https://doi.org/10.1137/S089548010444540X.
  28. Linda Cook, Jake Horsfield, Myriam Preissmann, Cléophée Robin, Paul Seymour, Ni Luh Dewi Sintiari, Nicolas Trotignon, and Kristina Vušković. Graphs with all holes the same length. arXiv, 2021. URL: http://arxiv.org/abs/2110.09970.
  29. Linda Cook and Paul Seymour. Detecting a long even hole. arXiv, 2020. URL: http://arxiv.org/abs/2009.05691.
  30. Gérard Cornuéjols, Xinming Liu, and Kristina Vušković. A polynomial algorithm for recognizing perfect graphs. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pages 20-27, 2003. URL: https://doi.org/10.1109/SFCS.2003.1238177.
  31. Murilo Vicente Gonçalves da Silva and Kristina Vušković. Decomposition of even-hole-free graphs with star cutsets and 2-joins. Journal of Combinatorial Theory, Series B, 103(1):144-183, 2013. URL: https://doi.org/10.1016/j.jctb.2012.10.001.
  32. Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Morten Stöckel. Finding even cycles faster via capped k-walks. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM Symposium on Theory of Computing, pages 112-120. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055459.
  33. Mina Dalirrooyfard, Thuy Duong Vuong, and Virginia Vassilevska Williams. Graph pattern detection: hardness for all induced patterns and faster non-induced cycles. In Proceedings of the 51st Annual ACM Symposium on Theory of Computing, pages 1167-1178, 2019. URL: https://doi.org/10.1145/3313276.3316329.
  34. David Eppstein. Finding the k shortest paths. SIAM Journal on Computing, 28(2):652-673, 1998. URL: https://doi.org/10.1137/S0097539795290477.
  35. Hazel Everett, Celina M. H. de Figueiredo, Cláudia Linhares Sales, Frédéric Maffray, Oscar Porto, and Bruce A. Reed. Path parity and perfection. Discrete Mathematics, 165-166:233-252, 1997. URL: https://doi.org/10.1016/S0012-365X(96)00174-4.
  36. Michael R. Fellows, Jan Kratochvíl, Matthias Middendorf, and Frank Pfeiffer. The complexity of induced minors and related problems. Algorithmica, 13(3):266-282, 1995. URL: https://doi.org/10.1007/BF01190507.
  37. J. Fonlupt and J.P. Uhry. Transformations which preserve perfectness and H-perfectness of graphs. In Achim Bachem, Martin Grötschel, and Bemhard Korte, editors, Bonn Workshop on Combinatorial Optimization, volume 66 of North-Holland Mathematics Studies, pages 83-95. North-Holland, 1982. URL: https://doi.org/10.1016/S0304-0208(08)72445-9.
  38. Zvi Galil and Oded Margalit. Witnesses for boolean matrix multiplication and for transitive closure. Journal of Complexity, 9(2):201-221, 1993. URL: https://doi.org/10.1006/jcom.1993.1014.
  39. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979. Google Scholar
  40. Serge Gaspers, Shenwei Huang, and Daniël Paulusma. Colouring square-free graphs without long induced paths. In Rolf Niedermeier and Brigitte Vallée, editors, Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, LIPIcs 96, pages 35.1-35.15, 2018. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.35.
  41. Emilio Di Giacomo, Giuseppe Liotta, and Tamara Mchedlidze. Lower and upper bounds for long induced paths in 3-connected planar graphs. Theoretical Computer Science, 636:47-55, 2016. URL: https://doi.org/10.1016/j.tcs.2016.04.034.
  42. Petr A. Golovach, Daniël Paulusma, and Erik Jan van Leeuwen. Induced disjoint paths in AT-free graphs. In Fedor V. Fomin and Petteri Kaski, editors, Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory, Lecture Notes in Computer Science 7357, pages 153-164, 2012. URL: https://doi.org/10.1007/978-3-642-31155-0_14.
  43. Robert Haas and Michael Hoffmann. Chordless paths through three vertices. Theoretical Computer Science, 351(3):360-371, 2006. URL: https://doi.org/10.1016/j.tcs.2005.10.021.
  44. Chính T. Hoàng, Marcin Kaminski, Joe Sawada, and R. Sritharan. Finding and listing induced paths and cycles. Discrete Applied Mathematics, 161(4-5):633-641, 2013. URL: https://doi.org/10.1016/j.dam.2012.01.024.
  45. Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Journal of the ACM, 48(4):723-760, July 2001. URL: https://doi.org/10.1145/502090.502095.
  46. Wen-Lian Hsu. Recognizing planar perfect graphs. Journal of the ACM, 34(2):255-288, 1987. URL: https://doi.org/10.1145/23005.31330.
  47. Lars Jaffke, O-joung Kwon, and Jan Arne Telle. Mim-width I. induced path problems. Discrete Applied Mathematics, 278:153-168, 2020. URL: https://doi.org/10.1016/j.dam.2019.06.026.
  48. David S. Johnson. The NP-completeness column. ACM Transactions on Algorithms, 1(1):160-176, 2005. URL: https://doi.org/10.1145/1077464.1077476.
  49. Marcin Kaminski and Naomi Nishimura. Finding an induced path of given parity in planar graphs in polynomial time. In Yuval Rabani, editor, Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 656-670, 2012. URL: https://doi.org/10.1137/1.9781611973099.55.
  50. Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Bruce A. Reed. The disjoint paths problem in quadratic time. Journal of Combinatorial Theory, Series B, 102(2):424-435, 2012. URL: https://doi.org/10.1016/j.jctb.2011.07.004.
  51. Matthias Kriesell. Induced paths in 5-connected graphs. Journal of Graph Theory, 36(1):52-58, 2001. URL: https://doi.org/10.1002/1097-0118(200101)36:1%3C52::AID-JGT5%3E3.0.CO;2-N.
  52. Kai-Yuan Lai, Hsueh-I Lu, and Mikkel Thorup. Three-in-a-tree in near linear time. In Proccedings of the 52nd Annual ACM Symposium on Theory of Computing, pages 1279-1292, 2020. URL: https://doi.org/10.1145/3357713.3384235.
  53. François Le Gall. Powers of tensors and fast matrix multiplication. In Katsusuke Nabeshima, Kosaku Nagasaka, Franz Winkler, and Ágnes Szántó, editors, Proceedings of the International Symposium on Symbolic and Algebraic Computation, pages 296-303, 2014. URL: https://doi.org/10.1145/2608628.2608664.
  54. Wei Liu and Nicolas Trotignon. The k-in-a-tree problem for graphs of girth at least k. Discrete Applied Mathematics, 158(15):1644-1649, 2010. URL: https://doi.org/10.1016/j.dam.2010.06.005.
  55. Henry Meyniel. A new property of critical imperfect graphs and some consequences. European Journal of Combinatorics, 8(3):313-316, 1987. URL: https://doi.org/10.1016/S0195-6698(87)80037-9.
  56. Oscar Porto. Even induced cycles in planar graphs. In Proceedings of the 1st Latin American Symposium on Theoretical Informatics, pages 417-429, 1992. URL: https://doi.org/10.1007/BFb0023845.
  57. Marko Radovanovic, Nicolas Trotignon, and Kristina Vušković. The (theta, wheel)-free graphs part IV: induced paths and cycles. Journal of Combinatorial Theory, Series B, 146:495-531, 2021. URL: https://doi.org/10.1016/j.jctb.2020.06.002.
  58. Neil Robertson and Paul D. Seymour. Graph minors. XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B, 63(1):65-110, 1995. URL: https://doi.org/10.1006/jctb.1995.1006.
  59. D. Rose, R. Tarjan, and G. Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing, 5(2):266-283, 1976. URL: https://doi.org/10.1137/0205021.
  60. Robert Endre Tarjan and Mihalis Yannakakis. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing, 13(3):566-579, 1984. see [Robert Endre Tarjan and Mihalis Yannakakis, 1985] for addendum. URL: https://doi.org/10.1137/0213035.
  61. Robert Endre Tarjan and Mihalis Yannakakis. Addendum: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing, 14(1):254-255, 1985. URL: https://doi.org/10.1137/0214020.
  62. Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pages 887-898, 2012. URL: https://doi.org/10.1145/2213977.2214056.
  63. Raphael Yuster and Uri Zwick. Finding even cycles even faster. SIAM Journal on Discrete Mathematics, 10(2):209-222, 1997. URL: https://doi.org/10.1137/S0895480194274133.
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