Counting induced subgraphs: A topological approach to #W[1]-hardness
We investigate the problem #IndSub(Φ) of counting all induced subgraphs of size k in a graph G that satisfy a given property Φ. This continues the work of Jerrum and Meeks who proved the problem to be #W[1]-hard for some families of properties which include (dis)connectedness [JCSS 15] and even- or...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Springer
2020
|
| _version_ | 1797084382986502144 |
|---|---|
| author | Roth, M Schmitt, J |
| author_facet | Roth, M Schmitt, J |
| author_sort | Roth, M |
| collection | OXFORD |
| description | We investigate the problem #IndSub(Φ) of counting all induced subgraphs of size k in a graph G that satisfy a given property Φ. This continues the work of Jerrum and Meeks who proved the problem to be #W[1]-hard for some families of properties which include (dis)connectedness [JCSS 15] and even- or oddness of the number of edges [Combinatorica 17]. Using the recent framework of graph motif parameters due to Curticapean, Dell and Marx [STOC 17], we discover that for monotone properties Φ, the problem #IndSub(Φ) is hard for #W[1] if the reduced Euler characteristic of the associated simplicial (graph) complex of Φ is non-zero. This observation links #IndSub(Φ) to Karp’s famous Evasiveness Conjecture, as every graph complex with non-vanishing reduced Euler characteristic is known to be evasive. Applying tools from the “topological approach to evasiveness” which was introduced in the seminal paper of Khan, Saks and Sturtevant [FOCS 83], we prove that #IndSub(Φ) is #W[1]-hard for every monotone property Φ that does not hold on the Hamilton cycle as well as for some monotone properties that hold on the Hamilton cycle such as being triangle-free or not k-edge-connected for k>2. Moreover, we show that for those properties #IndSub(Φ) can not be solved in time f(k)⋅no(k) for any computable function f unless the Exponential Time Hypothesis (ETH) fails. In the final part of the paper, we investigate non-monotone properties and prove that #IndSub(Φ) is #W[1]-hard if Φ is any non-trivial modularity constraint on the number of edges with respect to some prime q or if Φ enforces the presence of a fixed isolated subgraph. |
| first_indexed | 2024-03-07T01:54:39Z |
| format | Journal article |
| id | oxford-uuid:9b497962-b634-48c9-9b82-ec026e0dfeb0 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T01:54:39Z |
| publishDate | 2020 |
| publisher | Springer |
| record_format | dspace |
| spelling | oxford-uuid:9b497962-b634-48c9-9b82-ec026e0dfeb02022-03-27T00:27:51ZCounting induced subgraphs: A topological approach to #W[1]-hardnessJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:9b497962-b634-48c9-9b82-ec026e0dfeb0EnglishSymplectic Elements at OxfordSpringer2020Roth, MSchmitt, JWe investigate the problem #IndSub(Φ) of counting all induced subgraphs of size k in a graph G that satisfy a given property Φ. This continues the work of Jerrum and Meeks who proved the problem to be #W[1]-hard for some families of properties which include (dis)connectedness [JCSS 15] and even- or oddness of the number of edges [Combinatorica 17]. Using the recent framework of graph motif parameters due to Curticapean, Dell and Marx [STOC 17], we discover that for monotone properties Φ, the problem #IndSub(Φ) is hard for #W[1] if the reduced Euler characteristic of the associated simplicial (graph) complex of Φ is non-zero. This observation links #IndSub(Φ) to Karp’s famous Evasiveness Conjecture, as every graph complex with non-vanishing reduced Euler characteristic is known to be evasive. Applying tools from the “topological approach to evasiveness” which was introduced in the seminal paper of Khan, Saks and Sturtevant [FOCS 83], we prove that #IndSub(Φ) is #W[1]-hard for every monotone property Φ that does not hold on the Hamilton cycle as well as for some monotone properties that hold on the Hamilton cycle such as being triangle-free or not k-edge-connected for k>2. Moreover, we show that for those properties #IndSub(Φ) can not be solved in time f(k)⋅no(k) for any computable function f unless the Exponential Time Hypothesis (ETH) fails. In the final part of the paper, we investigate non-monotone properties and prove that #IndSub(Φ) is #W[1]-hard if Φ is any non-trivial modularity constraint on the number of edges with respect to some prime q or if Φ enforces the presence of a fixed isolated subgraph. |
| spellingShingle | Roth, M Schmitt, J Counting induced subgraphs: A topological approach to #W[1]-hardness |
| title | Counting induced subgraphs: A topological approach to #W[1]-hardness |
| title_full | Counting induced subgraphs: A topological approach to #W[1]-hardness |
| title_fullStr | Counting induced subgraphs: A topological approach to #W[1]-hardness |
| title_full_unstemmed | Counting induced subgraphs: A topological approach to #W[1]-hardness |
| title_short | Counting induced subgraphs: A topological approach to #W[1]-hardness |
| title_sort | counting induced subgraphs a topological approach to w 1 hardness |
| work_keys_str_mv | AT rothm countinginducedsubgraphsatopologicalapproachtow1hardness AT schmittj countinginducedsubgraphsatopologicalapproachtow1hardness |