Open access
Date
2022-02Type
- Journal Article
Abstract
We study the problem #INDSUB(Φ) of counting all induced subgraphs of size k in a graph G that satisfy the property Φ. It is shown that, given any graph property Φ that distinguishes independent sets from bicliques, #INDSUB(Φ) is hard for the class #W[1], i.e., the parameterized counting equivalent of NP. Under additional suitable density conditions on Φ, satisfied e.g. by non-trivial monotone properties on bipartite graphs, we strengthen #W[1]-hardness by establishing that #INDSUB(Φ) cannot be solved in time f(k)⋅no(k) for any computable function f, unless the Exponential Time Hypothesis fails. Finally, we observe that our results remain true even if the input graph G is restricted to be bipartite and counting is done modulo a fixed prime. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000520651Publication status
publishedExternal links
Journal / series
AlgorithmicaVolume
Pages / Article No.
Publisher
SpringerSubject
Counting complexity; Edge-transitive graphs; Graph homomorphisms; Induced subgraphs; Parameterized complexityMore
Show all metadata