Counting induced subgraphs: a topological approach to #W[1]-hardness. (English) Zbl 1452.68086
Summary: We investigate the problem \(\# \mathsf{IndSub} (\Phi)\) of counting all induced subgraphs of size \(k\) in a graph \(G\) that satisfy a given property \(\Phi\). This continues the work of
M. Jerrum and K. Meeks who proved the problem to be #W[1]-hard for some families of properties which include (dis)connectedness
[J. Comput. Syst. Sci. 81, No. 4, 702–716 (2015; Zbl 1320.68101)] and even- or oddness of the number of edges
[Combinatorica 37, No. 5, 965–990 (2017; Zbl 1413.68063)].
Using the recent framework of graph motif parameters due to
[R. Curticapean et al., in: Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC’17. New York, NY: Association for Computing Machinery (ACM). 210–223 (2017; Zbl 1369.05191)],
we discover that for monotone properties \(\Phi\), the problem \(\# \mathsf{IndSub} (\Phi)\) is hard for #W[1] if the reduced Euler characteristic of the associated simplicial (graph) complex of \(\Phi\) is non-zero. This observation links \(\# \mathsf{IndSub} (\Phi)\) to Karp’s famous Evasiveness Conjecture, as every graph complex with non-vanishing reduced Euler characteristic is known to be evasive. Applying tools from the “topological approach to evasiveness” which was introduced in the seminal paper of
J. Kahn et al. [Combinatorica 4, 297–306 (1984; Zbl 0577.05061)],
we prove that \(\# \mathsf{IndSub} (\Phi)\) is #W[1]-hard for every monotone property \(\Phi\) that does not hold on the Hamilton cycle as well as for some monotone properties that hold on the Hamilton cycle such as being triangle-free or not \(k\)-edge-connected for \(k > 2\). Moreover, we show that for those properties \(\# \mathsf{IndSub} (\Phi)\) can not be solved in time \(f(k) \cdot n^{o(k)}\) for any computable function \(f\) unless the Exponential Time Hypothesis (ETH) fails. In the final part of the paper, we investigate non-monotone properties and prove that \(\# \mathsf{IndSub} (\Phi)\) is #W[1]-hard if \(\Phi\) is any non-trivial modularity constraint on the number of edges with respect to some prime \(q\) or if \(\Phi\) enforces the presence of a fixed isolated subgraph.
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 05C30 | Enumeration in graph theory |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 05E45 | Combinatorial aspects of simplicial complexes |
| 68Q27 | Parameterized complexity, tractability and kernelization |
Keywords:
counting complexity; Euler characteristic; homomorphisms; parameterized complexity; simplicial complexesSoftware:
OEISReferences:
| [1] | Abrahamson, K.R., Downey, R.G., Fellows, M.R.: Fixed-parameter intractability II (extended abstract). In: STACS 93, 10th Annual Symposium on Theoretical Aspects of Computer Science, Würzburg, Germany, February 25-27, 1993, Proceedings, pp. 374-385 (1993) · Zbl 0799.68086 |
| [2] | Bredon, GE, Introduction to Compact Transformation Groups (1972), London: Academic Press, London · Zbl 0246.57017 |
| [3] | Chakrabarti, A.; Khot, S.; Shi, Y., Evasiveness of subgraph containment and related properties, SIAM J. Comput., 31, 3, 866-875 (2001) · Zbl 1051.68071 |
| [4] | Chen, J.; Chor, B.; Fellows, M.; Huang, X.; Juedes, DW; Kanj, IA; Xia, G., Tight lower bounds for certain parameterized NP-hard problems, Inf. Comput., 201, 2, 216-231 (2005) · Zbl 1161.68476 |
| [5] | Chen, J.; Huang, X.; Kanj, IA; Xia, G., Strong computational lower bounds via parameterized complexity, J. Comput. Syst. Sci., 72, 8, 1346-1367 (2006) · Zbl 1119.68092 |
| [6] | Chen, Y., Thurley, M., Weyer, M.: 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, pp. 587-596 (2008) · Zbl 1153.68387 |
| [7] | Curticapean, R.: The simple, little and slow things count: on parameterized counting complexity. Ph.D. thesis, Saarland University (2015) · Zbl 1409.68136 |
| [8] | Curticapean, R., Dell, H., Marx, D.: Homomorphisms are a good basis for counting small subgraphs. In: Proceedings of the 49th ACM Symposium on Theory of Computing, STOC, pp. 210-223 (2017) · Zbl 1369.05191 |
| [9] | Curticapean, R., Marx, D.: Complexity of counting subgraphs: Only the boundedness of the vertex-cover number counts. In: Proceedings of the 55th Annual Symposium on Foundations of Computer Science, FOCS, pp. 130-139 (2014) |
| [10] | Dalmau, V.; Jonsson, P., The complexity of counting homomorphisms seen from the other side, Theor. Comput. Sci., 329, 1, 315-323 (2004) · Zbl 1086.68054 |
| [11] | Flum, J.; Grohe, M., The parameterized complexity of counting problems, SIAM J. Comput., 33, 4, 892-922 (2004) · Zbl 1105.68042 |
| [12] | Flum, J., Grohe, M.: Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer, Inc., Secaucus (2006) · Zbl 1143.68016 |
| [13] | Grohe, M., The complexity of homomorphism and constraint satisfaction problems seen from the other side, J. ACM (JACM), 54, 1, 1 (2007) · Zbl 1312.68101 |
| [14] | Jerrum, M.; Meeks, K., The parameterised complexity of counting connected subgraphs and graph motifs, J. Comput. Syst. Sci., 81, 4, 702-716 (2015) · Zbl 1320.68101 |
| [15] | Jerrum, M.; Meeks, K., Some hard families of parameterized counting problems, TOCT, 7, 3, 11:1-11:18 (2015) · Zbl 1348.68066 |
| [16] | Jerrum, M.; Meeks, K., The parameterised complexity of counting even and odd induced subgraphs, Combinatorica, 37, 5, 965-990 (2017) · Zbl 1413.68063 |
| [17] | Jonsson, J., Simplicial Complexes of Graphs. Lecture Notes in Mathematics (2008), Berlin: Springer, Berlin · Zbl 1152.05001 |
| [18] | Kahn, J., Saks, M.E., Sturtevant, D.: A topological approach to evasiveness. In: 24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7-9 November 1983, pp. 31-33 (1983) · Zbl 0577.05061 |
| [19] | Ladner, RE, On the structure of polynomial time reducibility, J. ACM, 22, 1, 155-171 (1975) · Zbl 0322.68028 |
| [20] | Lovász, L., Large Networks and Graph Limits (2012), Providence: American Mathematical Society, Providence · Zbl 1292.05001 |
| [21] | Lutz, FH, Some results related to the evasiveness conjecture, J. Comb. Theory Ser. B, 81, 1, 110-124 (2001) · Zbl 1040.05027 |
| [22] | Meeks, K., The challenges of unbounded treewidth in parameterised subgraph counting problems, Discrete Appl. Math., 198, 170-194 (2016) · Zbl 1327.05244 |
| [23] | Miller, CA, Evasiveness of graph properties and topological fixed-point theorems, Found. Trends Theor. Comput. Sci., 7, 4, 337-415 (2013) · Zbl 1278.68019 |
| [24] | Oliver, R., Fixed-point sets of group actions on finite acyclic complexes, Comment. Math. Helvetici, 50, 1, 155-177 (1975) · Zbl 0304.57020 |
| [25] | Rivest, RL; Vuillemin, J., On recognizing graph properties from adjacency matrices, Theor. Comput. Sci., 3, 3, 371-384 (1976) · Zbl 0358.68079 |
| [26] | Roth, M.: Counting restricted homomorphisms via möbius inversion over matroid lattices. In: 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, pp. 63:1-63:14 (2017) · Zbl 1442.68075 |
| [27] | Sloane, N.: The On-Line Encyclopedia of Integer Sequences. URL: http://oeis.org (2018) · Zbl 1439.11001 |
| [28] | Smith, P., Fixed-point theorems for periodic transformations, Am. J. Math., 63, 1, 1-8 (1941) · JFM 67.0742.04 |
| [29] | Valiant, LG, The complexity of computing the permanent, Theor. Comput. Sci., 8, 189-201 (1979) · Zbl 0415.68008 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
