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

18^th May 2022, 14:00 GHOLTH223
Julian Dörfler
Saarland University

Abstract

We study the problem #IndSub(ϕ) of counting all induced subgraphs of
size k in a graph G that satisfy the property ϕ. This was known to be
#W[1]-hard for some families of properties ϕ including, among others,
connectivity, even- or oddness of the number of edges. 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 ϕ that is closed under the removal of
vertices and edges, and that is non-trivial for bipartite graphs, the
problem #IndSub(ϕ) 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.