The induced-subgraph counting hardness conjecture
Let be a computable graph property. For a graph and positive integer , let denote the problem of counting the -vertex subsets of that induce a graph satisfying , parameterized by . Suppose that there are infinitely many positive integers such that is neither true nor false on all graphs with vertices.
Induced-subgraph counting hardness conjecture. Then is -hard.
This conjecture proposes an explicit criterion for the -hardness of induced-subgraph counting problems. The known dichotomy gives that every such problem is either fixed-parameter tractable or -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
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.