Publication Overview

Marc Roth and Johannes Schmitt

Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness

We investigate the problem #IndSub(P) of counting all induced subgraphs of size k in a graph G that satisfy a given property P. This continues the work of Jerrum and Meeks who proved the problem to be #W[1]-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 P, the problem #IndSub(P) is hard for #W[1] if the reduced Euler characteristic of the associated simplicial (graph) complex of P is non-zero. This observation links #IndSub(P) 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 #IndSub(P) is #W[1]-hard for every monotone property P 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 #IndSub(P) can not be solved in time f(k)*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 #IndSub(P) is #W[1]-hard if P is any non-trivial modularity constraint on the number of edges with respect to some prime q or if P enforces the presence of a fixed isolated subgraph.

Published in: 13th International Symposium on Parameterized and Exact Computation, IPEC 2018, August 22-24, Helsinki, Finland
Year: 2018
Pages: 24:1-24:14