We investigate the problem @math of counting all induced subgraphs of size @math in a graph @math that satisfy a given property @math . This continues the work of Jerrum and Meeks who proved the problem to be @math -hard for some families of properties which include, among others, (dis)connectedness [JCSS 15] and even- or oddness of the number of edges [Combinatorica 17]. Using the recent framework of graph motif parameters due to Curticapean, Dell and Marx [STOC 17], we discover that for monotone properties @math , the problem @math is hard for @math if the reduced Euler characteristic of the associated simplicial (graph) complex of @math is non-zero. This observation links @math 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 Khan, Saks and Sturtevant [FOCS 83], we prove that @math is @math -hard for every monotone property @math 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 @math -edge-connected for @math . Moreover, we show that for those properties @math can not be solved in time @math for any computable function @math unless the Exponential Time Hypothesis (ETH) fails. In the final part of the paper, we investigate non-monotone properties and prove that @math is @math -hard if @math is any non-trivial modularity constraint on the number of edges with respect to some prime @math or if @math enforces the presence of a fixed isolated subgraph.
Jerrum and Meeks introduced and studied the problem @math for the following properties. @cite_11 they prove the problem to be @math -hard if @math is the property of being connected, which immediately follows from Theorem as @math and @math are equivalent We just need to substract one from @math to get the other. and the property of being disconnected is monotone and false for every cycle. @cite_4 hardness is established for the property of having an even (or odd) number of edges, which is subsumed by Theorem . Indeed, the case of @math follows already from Theorem as every term in the sum @math will have the same sign. @cite_16 Jerrum and Meeks prove the problem to be @math -hard whenever the edge-density of graphs in @math grows asymptotically slower than @math and in @cite_24 Meeks shows that whenever @math is co-monotone, i.e., @math is monotone, and the set of (edge-)minimal elements of @math has unbounded treewidth, the problem is hard as well.
@cite_24 @cite_16 @cite_4 @cite_11
2963279056 2964347561 1872333393 2962738766
Parameterised subgraph counting problems are the most thoroughly studied topic in the theory of parameterised counting, and there has been significant recent progress in this area. Many of the existing tractability results for parameterised problems which involve finding or counting subgraphs with particular properties rely on bounding the treewidth of these subgraphs in some sense; here, we prove a number of hardness results for the situation in which this bounded treewidth condition does not hold, resulting in dichotomies for some special cases of the general subgraph counting problem. The paper also gives a thorough survey of known results on this subject and the methods used, as well as discussing the relationships both between multicolour and uncoloured versions of subgraph counting problems, and between exact counting, approximate counting and the corresponding decision problems. We consider parameterized subgraph counting problems of the following form: given a graph G, how many k-tuples of its vertices induce a subgraph with a given property? A number of such problems are known to be #W[1]-complete; here, we substantially generalize some of these existing results by proving hardness for two large families of such problems. We demonstrate that it is #W[1]-hard to count the number of k-vertex subgraphs having any property where the number of distinct edge densities of labeled subgraphs that satisfy the property is o(k2). In the special case in which the property in question depends only on the number of edges in the subgraph, we give a strengthening of this result, which leads to our second family of hard problems. We consider the problem of counting, in a given graph, the number of induced k-vertex subgraphs which have an even number of edges, and also the complementary problem of counting the k-vertex induced subgraphs having an odd number of edges. We demonstrate that both problems are #W[1]-hard when parameterised by k, in fact proving a somewhat stronger result about counting subgraphs with a property that only holds for some subset of k-vertex subgraphs which have an even (respectively odd) number of edges. On the other hand, we show that each of the problems admits an FPTRAS. These approximation schemes are based on a surprising structural result, which exploits ideas from Ramsey theory. We introduce a family of parameterised counting problems on graphs, p-#Induced Subgraph With Property(Φ), which generalises a number of problems which have previously been studied. This paper focuses on the case in which Φ defines a family of graphs whose edge-minimal elements all have bounded treewidth; this includes the special case in which Φ describes the property of being connected. We show that exactly counting the number of connected induced k-vertex subgraphs in an n-vertex graph is #W[1]-hard, but on the other hand there exists an FPTRAS for the problem; more generally, we show that there exists an FPTRAS for p-#Induced Subgraph With Property(Φ) whenever Φ is monotone and all the minimal graphs satisfying Φ have bounded treewidth. We then apply these results to a counting version of the Graph Motif problem.