The induced-subgraph counting hardness conjecture

About 7 years old · traced to

Let Φ\Phi be a computable graph property. For a graph GG and positive integer kk, let #\textscIndSub(Φ)\#{\textsc{IndSub}}(\Phi) denote the problem of counting the kk-vertex subsets of GG that induce a graph satisfying Φ\Phi, parameterized by kk. Suppose that there are infinitely many positive integers kk such that Φ\Phi is neither true nor false on all graphs with kk vertices.

Induced-subgraph counting hardness conjecture. Then #\textscIndSub(Φ)\#{\textsc{IndSub}}(\Phi) is #W[1]\#{\mathsf{W[1]}}-hard.

This conjecture proposes an explicit criterion for the #W[1]\#{\mathsf{W[1]}}-hardness of induced-subgraph counting problems. The known dichotomy gives that every such problem is either fixed-parameter tractable or #W[1]\#{\mathsf{W[1]}}-hard, while the conjecture aims to characterize the hard cases; its status is not resolved in the supplied source.

References

Primary source

Julian Dörfler, Marc Roth, Johannes Schmitt and Philip Wellnitz, “Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness”, arXiv:1904.10479 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.