Document Open Access Logo

Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness

Authors Julian Dörfler , Marc Roth , Johannes Schmitt , Philip Wellnitz

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.26.pdf
  • Filesize: 493 kB
  • 14 pages

Document Identifiers

Author Details

Julian Dörfler
  • Saarbrücken Graduate School of Computer Science, Saarland Informatics Campus (SIC), Germany
Marc Roth
  • Cluster of Excellence (MMCI), Saarland Informatics Campus (SIC), Saarbrücken, Germany
Johannes Schmitt
  • ETH Zürich, Switzerland
Philip Wellnitz
  • Max Planck Institute for Informatics, Saarland Informatics Campus (SIC), Saarbrücken, Germany

Funding

  • Schmitt, Johannes: The third author has received funding from the European Research Council (ERC) under the EU’s Horizon 2020 research and innovation programme (No 786580).

Acknowledgements

We are very grateful to Radu Curticapean and Holger Dell for fruitful discussions and valuable feedback on early drafts of this work.

Cite AsGet BibTex

Julian Dörfler, Marc Roth, Johannes Schmitt, and Philip Wellnitz. Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.MFCS.2019.26

Abstract

We study the problem #IndSub(Phi) of counting all induced subgraphs of size k in a graph G that satisfy the property Phi. This problem was introduced by Jerrum and Meeks and shown to be #W[1]-hard when parameterized by k for some families of properties Phi including, among others, connectivity [JCSS 15] and even- or oddness of the number of edges [Combinatorica 17]. Very recently [IPEC 18], two of the authors introduced a novel technique for the complexity analysis of #IndSub(Phi), inspired by the "topological approach to evasiveness" of Kahn, Saks and Sturtevant [FOCS 83] and the framework of graph motif parameters due to Curticapean, Dell and Marx [STOC 17], allowing them to prove hardness of a wide range of properties Phi. In this work, we refine this technique for graph properties that are non-trivial on edge-transitive graphs with a prime power number of edges. In particular, we fully classify the case of monotone bipartite graph properties: It is shown that, given any graph property Phi that is closed under the removal of vertices and edges, and that is non-trivial for bipartite graphs, the problem #IndSub(Phi) is #W[1]-hard and cannot be solved in time f(k)* n^{o(k)} for any computable function f, unless the Exponential Time Hypothesis fails. This holds true even if the input graph is restricted to be bipartite and counting is done modulo a fixed prime. A similar result is shown for properties that are closed under the removal of edges only.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Problems, reductions and completeness
  • Mathematics of computing → Combinatorics
  • Mathematics of computing → Graph theory
Keywords
  • counting complexity
  • edge-transitive graphs
  • graph homomorphisms
  • induced subgraphs
  • parameterized complexity

Metrics

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

Related Versions

References

  1. Shreeram S. Abhyankar. Lectures on algebra. Vol. I. World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2006. URL: https://doi.org/10.1142/9789812773449.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. Jack Edmonds. Paths, Trees, and Flowers. Canadian Journal of Mathematics, 17:449–467, 1965. URL: https://doi.org/10.4153/CJM-1965-045-4.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.
  14. Serge Lang. Algebra. Graduate Texts in Mathematics. Springer New York, 2005. URL: https://doi.org/10.1007/978-1-4613-0041-0.
  15. 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.
  16. Catherine McCartin. Parameterized counting problems. Ann. Pure Appl. Logic, 138(1-3):147-182, 2006. URL: https://doi.org/10.1016/j.apal.2005.06.010.
  17. 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.
  18. Carl A. Miller. Evasiveness of Graph Properties and Topological Fixed-Point Theorems. Foundations and Trends in Theoretical Computer Science, 7(4):337-415, 2013. URL: https://doi.org/10.1561/0400000055.
  19. Ronald L. Rivest and Jean Vuillemin. On recognizing graph properties from adjacency matrices. Theoret. Comput. Sci., 3(3):371-384, 1976/77. URL: https://doi.org/10.1016/0304-3975(76)90053-0.
  20. Marc Roth and Johannes Schmitt. Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness. In 13th International Symposium on Parameterized and Exact Computation, IPEC 2018, August 20-24, 2018, Helsinki, Finland, pages 24:1-24:14, 2018. URL: https://doi.org/10.4230/LIPIcs.IPEC.2018.24.
  21. 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.
  22. 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.
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