We study the problem $$\#\textsc {IndSub}(\varPhi )$$ # I N D S U B ( Φ ) of counting all induced subgraphs of size k in a graph G that… Click to show full abstract
We study the problem $$\#\textsc {IndSub}(\varPhi )$$#INDSUB(Φ) of counting all induced subgraphs of size k in a graph G that satisfy the property $$\varPhi $$Φ. It is shown that, given any graph property $$\varPhi $$Φ that distinguishes independent sets from bicliques, $$\#\textsc {IndSub}(\varPhi )$$#INDSUB(Φ) is hard for the class $$\#\mathsf {W[1]}$$#W[1], i.e., the parameterized counting equivalent of $${{\mathsf {N}}}{{\mathsf {P}}}$$NP. Under additional suitable density conditions on $$\varPhi $$Φ, satisfied e.g. by non-trivial monotone properties on bipartite graphs, we strengthen $$\#\mathsf {W[1]}$$#W[1]-hardness by establishing that $$\#\textsc {IndSub}(\varPhi )$$#INDSUB(Φ) cannot be solved in time $$f(k)\cdot n^{o(k)}$$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.
Share on Social Media:
  
        
        
        
Sign Up to like & get recommendations! 2
Related content
More Information
            
News
            
Social Media
            
Video
            
Recommended
               
Click one of the above tabs to view related content.