Document Open Access Logo

Current Algorithms for Detecting Subgraphs of Bounded Treewidth Are Probably Optimal

Authors Karl Bringmann, Jasper Slusallek

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2021.40.pdf
  • Filesize: 0.76 MB
  • 16 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Computational complexity and cryptography
Keywords
  • subgraph isomorphism
  • treewidth
  • fine-grained complexity
  • hyperclique

Metrics

Abstract

The Subgraph Isomorphism problem is of considerable importance in computer science. We examine the problem when the pattern graph H is of bounded treewidth, as occurs in a variety of applications. This problem has a well-known algorithm via color-coding that runs in time O(n^{tw(H)+1}) [Alon, Yuster, Zwick'95], where n is the number of vertices of the host graph G. While there are pattern graphs known for which Subgraph Isomorphism can be solved in an improved running time of O(n^{tw(H)+1-ε}) or even faster (e.g. for k-cliques), it is not known whether such improvements are possible for all patterns. The only known lower bound rules out time n^{o(tw(H) / log(tw(H)))} for any class of patterns of unbounded treewidth assuming the Exponential Time Hypothesis [Marx'07].
In this paper, we demonstrate the existence of maximally hard pattern graphs H that require time n^{tw(H)+1-o(1)}. Specifically, under the Strong Exponential Time Hypothesis (SETH), a standard assumption from fine-grained complexity theory, we prove the following asymptotic statement for large treewidth t: 
For any ε > 0 there exists t ≥ 3 and a pattern graph H of treewidth t such that Subgraph Isomorphism on pattern H has no algorithm running in time O(n^{t+1-ε}). 
Under the more recent 3-uniform Hyperclique hypothesis, we even obtain tight lower bounds for each specific treewidth t ≥ 3: 
For any t ≥ 3 there exists a pattern graph H of treewidth t such that for any ε > 0 Subgraph Isomorphism on pattern H has no algorithm running in time O(n^{t+1-ε}). 
In addition to these main results, we explore (1) colored and uncolored problem variants (and why they are equivalent for most cases), (2) Subgraph Isomorphism for tw < 3, (3) Subgraph Isomorphism parameterized by pathwidth instead of treewidth, and (4) a weighted variant that we call Exact Weight Subgraph Isomorphism, for which we examine pseudo-polynomial time algorithms. For many of these settings we obtain similarly tight upper and lower bounds.

Cite As Get BibTex

Karl Bringmann and Jasper Slusallek. Current Algorithms for Detecting Subgraphs of Bounded Treewidth Are Probably Optimal. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.40

Author Details

Karl Bringmann
  • Saarland University, Saarland Informatics Campus, Saarbrücken, Germany
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany
Jasper Slusallek
  • Saarland University, Saarland Informatics Campus, Saarbrücken, Germany

Funding

  • Bringmann, Karl: This work is part of the project TIPEA that has received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No. 850979).

References

  1. Amir Abboud and Greg Bodwin. The 4/3 additive spanner exponent is tight. Journal of the ACM (JACM), 64(4):1-20, 2017. Google Scholar
  2. Amir Abboud, Greg Bodwin, and Seth Pettie. A hierarchy of lower bounds for sublinear additive spanners. SIAM Journal on Computing, 47(6):2203-2236, 2018. Google Scholar
  3. Amir Abboud, Karl Bringmann, Danny Hermelin, and Dvir Shabtay. SETH-based lower bounds for Subset Sum and Bicriteria Path. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 41-57. SIAM, 2019. Google Scholar
  4. Amir Abboud, Karl Bringmann, Danny Hermelin, and Dvir Shabtay. Scheduling lower bounds via AND Subset Sum. arXiv preprint, 2020. URL: http://arxiv.org/abs/2003.07113.
  5. Amir Abboud and Kevin Lewi. Exact weight subgraphs and the k-SUM conjecture. In International Colloquium on Automata, Languages, and Programming, pages 1-12. Springer, 2013. Google Scholar
  6. Amir Abboud, Kevin Lewi, and Ryan Williams. Losing weight by gaining edges. In European Symposium on Algorithms, pages 1-12. Springer, 2014. Google Scholar
  7. Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching triangles and basing hardness on an extremely popular conjecture. SIAM Journal on Computing, 47(3):1098-1122, 2018. Google Scholar
  8. Noga Alon. Testing subgraphs in large graphs. Random Structures & Algorithms, 21(3-4):359-370, 2002. Google Scholar
  9. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM (JACM), 42(4):844-856, 1995. Google Scholar
  10. Omid Amini, Fedor V Fomin, and Saket Saurabh. Counting subgraphs via homomorphisms. In International Colloquium on Automata, Languages, and Programming, pages 71-82. Springer, 2009. Google Scholar
  11. Zhao An, Qilong Feng, Iyad Kanj, and Ge Xia. The complexity of tree partitioning. In Workshop on Algorithms and Data Structures, pages 37-48. Springer, 2017. Google Scholar
  12. MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Saeed Seddighin, and Cliff Stein. Fast algorithms for knapsack via convolution and prediction. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1269-1282, 2018. Google Scholar
  13. Felix A Behrend. On sets of integers which contain no three terms in arithmetical progression. Proceedings of the National Academy of Sciences of the United States of America, 32(12):331, 1946. Google Scholar
  14. Hans L Bodlaender. A tourist guide through treewidth. Acta cybernetica, 11(1-2):1, 1994. Google Scholar
  15. Hans L Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theoretical computer science, 209(1-2):1-45, 1998. Google Scholar
  16. Hans L Bodlaender. Discovering treewidth. In International Conference on Current Trends in Theory and Practice of Computer Science, pages 1-16. Springer, 2005. Google Scholar
  17. David Bremner, Timothy M Chan, Erik D Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, and Perouz Taslakian. Necklaces, convolutions, and x+ y. In European Symposium on Algorithms, pages 160-171. Springer, 2006. Google Scholar
  18. Karl Bringmann. A near-linear pseudopolynomial time algorithm for Subset Sum. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1073-1084. SIAM, 2017. Google Scholar
  19. Danilo Bruschi, Lorenzo Martignoni, and Mattia Monga. Detecting self-mutating malware using control-flow graph matching. In International conference on detection of intrusions and malware, and vulnerability assessment, pages 129-143. Springer, 2006. Google Scholar
  20. Timothy M Chan and Moshe Lewenstein. Clustered integer 3SUM via additive combinatorics. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 31-40, 2015. Google Scholar
  21. Don Coppersmith. Rapid multiplication of rectangular matrices. SIAM Journal on Computing, 11(3):467-471, 1982. Google Scholar
  22. Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 1-6, 1987. Google Scholar
  23. Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2009. Google Scholar
  24. Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 210-223, 2017. Google Scholar
  25. 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 SIGACT Symposium on Theory of Computing, pages 1167-1178, 2019. Google Scholar
  26. Bartłomiej Dudek, Paweł Gawrychowski, and Tatiana Starikovskaya. All non-trivial variants of 3-LDT are equivalent. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 974-981, 2020. Google Scholar
  27. Friedrich Eisenbrand and Fabrizio Grandoni. On the complexity of fixed parameter clique and dominating set. Theoretical Computer Science, 326(1-3):57-67, 2004. Google Scholar
  28. 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. Google Scholar
  29. Fedor V Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh, and BV Raghavendra Rao. Faster algorithms for finding and counting subgraphs. Journal of Computer and System Sciences, 78(3):698-706, 2012. Google Scholar
  30. François Le Gall and Florent Urrutia. Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1029-1046. SIAM, 2018. Google Scholar
  31. Edinah K Gnang, Ahmed Elgammal, and Vladimir Retakh. A spectral theory for tensors. In Annales de la Faculté des sciences de Toulouse: Mathématiques, volume 20, pages 801-841, 2011. Google Scholar
  32. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. Google Scholar
  33. Klaus Jansen, Stefan Kratsch, Dániel Marx, and Ildikó Schlotter. Bin packing with fixed number of bins revisited. Journal of Computer and System Sciences, 79(1):39-49, 2013. Google Scholar
  34. Konstantinos Koiliaris and Chao Xu. A faster pseudopolynomial time algorithm for Subset Sum. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1062-1072. SIAM, 2017. Google Scholar
  35. Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider. On the fine-grained complexity of one-dimensional dynamic programming. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  36. François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th international symposium on symbolic and algebraic computation, pages 296-303, 2014. Google Scholar
  37. Yuan Li, Alexander Razborov, and Benjamin Rossman. On the AC⁰ complexity of Subgraph Isomorphism. SIAM Journal on Computing, 46(3):936-971, 2017. Google Scholar
  38. Andrea Lincoln, Virginia Vassilevska Williams, and Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1236-1252. SIAM, 2018. Google Scholar
  39. Josef Malík, Ondřej Suchy, and Tomáš Valla. Efficient implementation of Color Coding algorithm for Subgraph Isomorphism problem. In International Symposium on Experimental Algorithms, pages 283-299. Springer, 2019. Google Scholar
  40. Dániel Marx. Can you beat treewidth? In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pages 169-179. IEEE, 2007. Google Scholar
  41. Dániel Marx and Michal Pilipczuk. Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask). In Ernst W. Mayr and Natacha Portier, editors, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), volume 25 of Leibniz International Proceedings in Informatics (LIPIcs), pages 542-553, Dagstuhl, Germany, 2014. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.STACS.2014.542.
  42. Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Network motifs: simple building blocks of complex networks. Science, 298(5594):824-827, 2002. Google Scholar
  43. Jaroslav Nešetřil and Svatopluk Poljak. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae, 26(2):415-419, 1985. Google Scholar
  44. Kevin Pratt. Waring rank, parameterized and exact algorithms. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 806-823. IEEE, 2019. Google Scholar
  45. Gregory Rosenthal. Beating treewidth for average-case subgraph isomorphism. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  46. Paul D Seymour and Robin Thomas. Graph searching and a min-max theorem for tree-width. Journal of Combinatorial Theory, Series B, 58(1):22-33, 1993. Google Scholar
  47. Edward H Sussenguth. A graph-theoretic algorithm for matching chemical structures. Journal of Chemical Documentation, 5(1):36-43, 1965. Google Scholar
  48. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science, 348(2-3):357-365, 2005. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact