Document Open Access Logo

Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders

Authors Marc Roth , Johannes Schmitt , Philip Wellnitz

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.108.pdf
  • Filesize: 0.82 MB
  • 16 pages

Document Identifiers

Author Details

Marc Roth
  • Merton College, University of Oxford, UK
Johannes Schmitt
  • Mathematical Institute, University of Bonn, Germany
Philip Wellnitz
  • Max Planck Institute for Informatics, Saarland Informatics Campus (SIC), Saarbrücken, Germany

Funding

  • Schmitt, Johannes: The second author was supported by the SNF early postdoc mobility grant 184245.

Acknowledgements

We thank Alina Vdovina and Norbert Peyerimhoff for explaining their construction of 2-group Cayley graph expanders [Peyerimhoff and Vdovina, 2011]. We thank Johannes Lengler and Holger Dell for helpful discussions on early drafts of this work. The second author was supported by the SNF early postdoc mobility grant 184245 and thanks the Max Planck Institute for Mathematics in Bonn for its hospitality.

Cite As Get BibTex

Marc Roth, Johannes Schmitt, and Philip Wellnitz. Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 108:1-108:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.108

Abstract

Given a graph property Φ, we consider the problem EdgeSub(Φ), where the input is a pair of a graph G and a positive integer k, and the task is to decide whether G contains a k-edge subgraph that satisfies Φ. Specifically, we study the parameterized complexity of EdgeSub(Φ) and of its counting problem #EdgeSub(Φ) with respect to both approximate and exact counting. We obtain a complete picture for minor-closed properties Φ: the decision problem EdgeSub(Φ) always admits an FPT ("fixed-parameter tractable") algorithm and the counting problem #EdgeSub(Φ) always admits an FPTRAS ("fixed-parameter tractable randomized approximation scheme"). For exact counting, we present an exhaustive and explicit criterion on the property Φ which, if satisfied, yields fixed-parameter tractability and otherwise #W[1]-hardness. Additionally, most of our hardness results come with an almost tight conditional lower bound under the so-called Exponential Time Hypothesis, ruling out algorithms for #EdgeSub(Φ) that run in time f(k)⋅ |G|^{o(k/log k)} for any computable function f.
As a main technical result, we gain a complete understanding of the coefficients of toroidal grids and selected Cayley graph expanders in the homomorphism basis of #EdgeSub(Φ). This allows us to establish hardness of exact counting using the Complexity Monotonicity framework due to Curticapean, Dell and Marx (STOC'17). This approach does not only apply to #EdgeSub(Φ) but also to the more general problem of computing weighted linear combinations of subgraph counts. As a special case of such a linear combination, we introduce a parameterized variant of the Tutte Polynomial T^k_G of a graph G, to which many known combinatorial interpretations of values of the (classical) Tutte Polynomial can be extended. As an example, T^k_G(2,1) corresponds to the number of k-forests in the graph G. Our techniques allow us to completely understand the parameterized complexity of computing the evaluation of T^k_G at every pair of rational coordinates (x,y). In particular, our results give a new proof for the #W[1]-hardness of the problem of counting k-forests in a graph.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Counting complexity
  • parameterized complexity
  • Tutte polynomial

Metrics

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

Related Versions

References

  1. Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, and S. Cenk Sahinalp. Biomolecular network motif counting and discovery by color coding. Bioinformatics, 24(13):i241-i249, July 2008. URL: https://doi.org/10.1093/bioinformatics/btn163.
  2. Noga Alon, Alan M. Frieze, and Dominic Welsh. Polynomial Time Randomized Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case. Random Struct. Algorithms, 6(4):459-478, 1995. URL: https://doi.org/10.1002/rsa.3240060409.
  3. Noga Alon, Raphael Yuster, and Uri Zwick. Color-Coding. J. ACM, 42(4):844-856, 1995. URL: https://doi.org/10.1145/210332.210337.
  4. Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant. Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1-12. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316385.
  5. Vikraman Arvind and Venkatesh Raman. Approximation Algorithms for Some Parameterized Counting Problems. In Algorithms and Computation, 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21-23, 2002, Proceedings, pages 453-464, 2002. URL: https://doi.org/10.1007/3-540-36136-7_40.
  6. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Computing the Tutte Polynomial in Vertex-Exponential Time. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 677-686. IEEE Computer Society, 2008. URL: https://doi.org/10.1109/FOCS.2008.40.
  7. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Narrow sieves for parameterized paths and packings. J. Comput. Syst. Sci., 87:119-139, 2017. URL: https://doi.org/10.1016/j.jcss.2017.03.003.
  8. Andreas Björklund and Petteri Kaski. The Fine-Grained Complexity of Computing the Tutte Polynomial of a Linear Matroid. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Alexandria, VA, USA, January 10-13, 2021, to appear. Google Scholar
  9. Cornelius Brand, Holger Dell, and Thore Husfeldt. Extensor-coding. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 151-164, 2018. URL: https://doi.org/10.1145/3188745.3188902.
  10. Cornelius Brand, Holger Dell, and Marc Roth. Fine-Grained Dichotomies for the Tutte Plane and Boolean #CSP. Algorithmica, 81(2):541-556, 2019. URL: https://doi.org/10.1007/s00453-018-0472-z.
  11. Cornelius Brand and Marc Roth. Parameterized Counting of Trees, Forests and Matroid Bases. In Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June 8-12, 2017, Proceedings, pages 85-98, 2017. URL: https://doi.org/10.1007/978-3-319-58747-9_10.
  12. Ashok K. Chandra and Philip M. Merlin. Optimal Implementation of Conjunctive Queries in Relational Data Bases. In Proceedings of the 9th Annual ACM Symposium on Theory of Computing, May 4-6, 1977, Boulder, Colorado, USA, pages 77-90, 1977. URL: https://doi.org/10.1145/800105.803397.
  13. Hubie Chen and Stefan Mengel. Counting Answers to Existential Positive Queries: A Complexity Classification. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 315-326, 2016. URL: https://doi.org/10.1145/2902251.2902279.
  14. Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, and Ge Xia. Tight lower bounds for certain parameterized NP-hard problems. Inf. Comput., 201(2):216-231, 2005. URL: https://doi.org/10.1016/j.ic.2005.05.001.
  15. Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia. Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci., 72(8):1346-1367, 2006. URL: https://doi.org/10.1016/j.jcss.2006.04.007.
  16. Jianer Chen, Joachim Kneis, Songjian Lu, Daniel Mölle, Stefan Richter, Peter Rossmanith, Sing-Hoi Sze, and Fenghui Zhang. Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms. SIAM Journal on Computing, 38(6):2526-2547, 2009. URL: https://doi.org/10.1137/080716475.
  17. Yijia Chen, Marc Thurley, and Mark Weyer. Understanding the Complexity of Induced Subgraph Isomorphisms. In 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, pages 587-596, 2008. URL: https://doi.org/10.1007/978-3-540-70575-8_48.
  18. Stephen A. Cook. The Complexity of Theorem-Proving Procedures. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, May 3-5, 1971, Shaker Heights, Ohio, USA, pages 151-158, 1971. URL: https://doi.org/10.1145/800157.805047.
  19. Derek G. Corneil and C. C. Gotlieb. An Efficient Algorithm for Graph Isomorphism. J. ACM, 17(1):51-64, 1970. URL: https://doi.org/10.1145/321556.321562.
  20. Radu Curticapean. Counting matchings of size k is w[1]-hard. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, volume 7965 of Lecture Notes in Computer Science, pages 352-363. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-39206-1_30.
  21. 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, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 210-223, 2017. URL: https://doi.org/10.1145/3055399.3055502.
  22. Radu Curticapean and Dániel Marx. Complexity of Counting Subgraphs: Only the Boundedness of the Vertex-Cover Number Counts. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 130-139, 2014. URL: https://doi.org/10.1109/FOCS.2014.22.
  23. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  24. Víctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side. Theor. Comput. Sci., 329(1-3):315-323, 2004. URL: https://doi.org/10.1016/j.tcs.2004.08.008.
  25. Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlen. Exponential Time Complexity of the Permanent and the Tutte Polynomial. ACM Trans. Algorithms, 10(4):21:1-21:32, 2014. URL: https://doi.org/10.1145/2635812.
  26. Holger Dell, John Lapinskas, and Kitty Meeks. Approximately counting and sampling small witnesses using a colourful decision oracle. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2201-2211. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.135.
  27. Holger Dell, Marc Roth, and Philip Wellnitz. Counting Answers to Existential Questions. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, pages 113:1-113:15, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.113.
  28. Julian Dörfler, Marc Roth, Johannes Schmitt, and Philip Wellnitz. Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness. In Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen, editors, 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, volume 138 of LIPIcs, pages 26:1-26:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.26.
  29. Rodney G. Downey and Michael R. Fellows. Fixed-Parameter Tractability and Completeness I: Basic Results. SIAM J. Comput., 24(4):873-921, 1995. URL: https://doi.org/10.1137/S0097539792228228.
  30. Rodney G. Downey and Michael R. Fellows. Fixed-Parameter Tractability and Completeness II: On Completeness for W[1]. Theor. Comput. Sci., 141(1&2):109-131, 1995. URL: https://doi.org/10.1016/0304-3975(94)00097-3.
  31. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  32. Arnaud Durand and Stefan Mengel. Structural Tractability of Counting of Solutions to Conjunctive Queries. Theory Comput. Syst., 57(4):1202-1249, 2015. URL: https://doi.org/10.1007/s00224-014-9543-y.
  33. Jack Edmonds. Paths, Trees, and Flowers. Canadian Journal of Mathematics, 17:449-467, 1965. URL: https://doi.org/10.4153/CJM-1965-045-4.
  34. Jörg Flum and Martin Grohe. The Parameterized Complexity of Counting Problems. SIAM J. Comput., 33(4):892-922, 2004. URL: https://doi.org/10.1137/S0097539703427203.
  35. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. URL: https://doi.org/10.1007/3-540-29953-X.
  36. Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 142-151. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.10.
  37. Leslie Ann Goldberg and Mark Jerrum. The Complexity of Computing the Sign of the Tutte Polynomial. SIAM J. Comput., 43(6):1921-1952, 2014. URL: https://doi.org/10.1137/12088330X.
  38. Joshua A. Grochow and Manolis Kellis. Network Motif Discovery Using Subgraph Enumeration and Symmetry-Breaking. In Terry Speed and Haiyan Huang, editors, Research in Computational Molecular Biology, pages 92-106, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. Google Scholar
  39. Martin Grohe. Parameterized Complexity for the Database Theorist. SIGMOD Rec., 31(4):86-96, 2002. URL: https://doi.org/10.1145/637411.637428.
  40. Martin Grohe, Thomas Schwentick, and Luc Segoufin. When is the evaluation of conjunctive queries tractable? In Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 657-666, 2001. URL: https://doi.org/10.1145/380752.380867.
  41. Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727.
  42. F. Jaeger, Dirk L. Vertigan, and Dominic J. A. Welsh. On the computational complexity of the Jones and Tutte polynomials. Mathematical Proceedings of the Cambridge Philosophical Society, 108(1):35–53, 1990. URL: https://doi.org/10.1017/S0305004100068936.
  43. Mark Jerrum and Kitty Meeks. The parameterised complexity of counting connected subgraphs and graph motifs. J. Comput. Syst. Sci., 81(4):702-716, 2015. URL: https://doi.org/10.1016/j.jcss.2014.11.015.
  44. Mark Jerrum and Kitty Meeks. Some Hard Families of Parameterized Counting Problems. TOCT, 7(3):11:1-11:18, 2015. URL: https://doi.org/10.1145/2786017.
  45. Mark Jerrum and Kitty Meeks. The parameterised complexity of counting even and odd induced subgraphs. Combinatorica, 37(5):965-990, 2017. URL: https://doi.org/10.1007/s00493-016-3338-5.
  46. Jeff Kahn, Michael E. Saks, and Dean Sturtevant. A topological approach to evasiveness. Combinatorica, 4(4):297-306, 1984. URL: https://doi.org/10.1007/BF02579140.
  47. Subhash Khot and Venkatesh Raman. Parameterized complexity of finding subgraphs with hereditary properties. Theor. Comput. Sci., 289(2):997-1008, 2002. URL: https://doi.org/10.1016/S0304-3975(01)00414-5.
  48. Bingkai Lin. The Parameterized Complexity of the k-Biclique Problem. J. ACM, 65(5):34:1-34:23, 2018. URL: https://doi.org/10.1145/3212622.
  49. László Lovász. Large Networks and Graph Limits, volume 60 of Colloquium Publications. American Mathematical Society, 2012. URL: http://www.ams.org/bookstore-getitem/item=COLL-60.
  50. Dániel Marx. Can You Beat Treewidth? Theory of Computing, 6(1):85-112, 2010. URL: https://doi.org/10.4086/toc.2010.v006a005.
  51. Kitty Meeks. The challenges of unbounded treewidth in parameterised subgraph counting problems. Discrete Applied Mathematics, 198:170-194, 2016. URL: https://doi.org/10.1016/j.dam.2015.06.019.
  52. R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. Network Motifs: Simple Building Blocks of Complex Networks. Science, 298(5594):824-827, 2002. URL: https://doi.org/10.1126/science.298.5594.824.
  53. Ron Milo, Shalev Itzkovitz, Nadav Kashtan, Reuven Levitt, Shai Shen-Orr, Inbal Ayzenshtat, Michal Sheffer, and Uri Alon. Superfamilies of evolved and designed networks. Science, 303(5663):1538-1542, 2004. URL: https://doi.org/10.1126/science.1089167.
  54. Norbert Peyerimhoff and Alina Vdovina. Cayley graph expanders and groups of finite width. J. Pure Appl. Algebra, 215(11):2780-2788, 2011. URL: https://doi.org/10.1016/j.jpaa.2011.03.018.
  55. Jürgen Plehn and Bernd Voigt. Finding minimally weighted subgraphs. In Rolf H. Möhring, editor, Graph-Theoretic Concepts in Computer Science, 16rd International Workshop, WG '90, Berlin, Germany, June 20-22, 1990, Proceedings, volume 484 of Lecture Notes in Computer Science, pages 18-29. Springer, 1990. URL: https://doi.org/10.1007/3-540-53832-1_28.
  56. Ofer Rahat, Uri Alon, Yaakov Levy, and Gideon Schreiber. Understanding hydrogen-bond patterns in proteins using network motifs. Bioinformatics, 25(22):2921-2928, September 2009. URL: https://doi.org/10.1093/bioinformatics/btp541.
  57. Marc Roth and Johannes Schmitt. Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness. Algorithmica, 82(8):2267-2291, 2020. URL: https://doi.org/10.1007/s00453-020-00676-9.
  58. Marc Roth, Johannes Schmitt, and Philip Wellnitz. Counting Small Induced Subgraphs Satisfying Monotone Properties. 61th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, to appear. Google Scholar
  59. Benjamin Schiller, Sven Jager, Kay Hamacher, and Thorsten Strufe. StreaM - A Stream-Based Algorithm for Counting Motifs in Dynamic Graphs. In Adrian-Horia Dediu, Francisco Hernández-Quiroz, Carlos Martín-Vide, and David A. Rosenblueth, editors, Algorithms for Computational Biology, pages 53-67, Cham, 2015. Springer International Publishing. Google Scholar
  60. Falk Schreiber and Henning Schwöbbermeyer. Frequency Concepts and Pattern Detection for the Analysis of Motifs in Networks. In Corrado Priami, Emanuela Merelli, Pablo Gonzalez, and Andrea Omicini, editors, Transactions on Computational Systems Biology III, pages 89-104, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. Google Scholar
  61. Seinosuke Toda. PP is as Hard as the Polynomial-Time Hierarchy. SIAM J. Comput., 20(5):865-877, 1991. URL: https://doi.org/10.1137/0220053.
  62. Julian R. Ullmann. An algorithm for subgraph isomorphism. J. ACM, 23(1):31-42, 1976. URL: https://doi.org/10.1145/321921.321925.
  63. Leslie G. Valiant. The Complexity of Computing the Permanent. Theor. Comput. Sci., 8:189-201, 1979. URL: https://doi.org/10.1016/0304-3975(79)90044-6.
  64. Leslie G. Valiant. The Complexity of Enumeration and Reliability Problems. SIAM J. Comput., 8(3):410-421, 1979. URL: https://doi.org/10.1137/0208032.
  65. Dirk Vertigan. Bicycle Dimension and Special Points of the Tutte Polynomial. J. Comb. Theory Ser. B, 74(2):378–396, 1998. URL: https://doi.org/10.1006/jctb.1998.1860.
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