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
|