Counting Small Induced Subgraphs Satisfying Monotone Properties

04/14/2020
βˆ™
by   Marc Roth, et al.
βˆ™
0
βˆ™

Given a graph property Ξ¦, the problem #π–¨π—‡π–½π–²π—Žπ–»(Ξ¦) asks, on input a graph G and a positive integer k, to compute the number of induced subgraphs of size k in G that satisfy Ξ¦. The search for explicit criteria on Ξ¦ ensuring that #π–¨π—‡π–½π–²π—Žπ–»(Ξ¦) is hard was initiated by Jerrum and Meeks [J. Comput. Syst. Sci. 15] and is part of the major line of research on counting small patterns in graphs. However, apart from an implicit result due to Curticapean, Dell and Marx [STOC 17] proving that a full classification into "easy" and "hard" properties is possible and some partial results on edge-monotone properties due to Meeks [Discret. Appl. Math. 16] and DΓΆrfler et al. [MFCS 19], not much is known. In this work, we fully answer and explicitly classify the case of monotone, that is subgraph-closed, properties: We show that for any non-trivial monotone property Ξ¦, the problem #π–¨π—‡π–½π–²π—Žπ–»(Ξ¦) cannot be solved in time f(k)Β· |V(G)|^o(k/ log^1/2(k)) for any function f, unless the Exponential Time Hypothesis fails. By this, we establish that any significant improvement over the brute-force approach is unlikely; in the language of parameterized complexity, we also obtain a #𝖢[1]-completeness result.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset