Counting Small Induced Subgraphs Satisfying Monotone Properties

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 P, the problem #IndSub(P) cannot be solved in time f(k) * |V(G)|^o(k/sqrt(log k)) for any function f, unless the Exponential Time Hypothesis fails. By this, we establish that any signicant improvement over the brute-force approach is unlikely; in the language of parameterized complexity, we also obtain a #W[1]-completeness result.

The methods we develop for the above problem also allow us to prove a conjecture by Jerrum and Meeks [TOCT 15, Combinatorica 19]: #IndSub(P) is #W[1]-complete if P is a non-trivial graph property only depending on the number of edges of the graph.


---------------
Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.