Counting small induced subgraphs satisfying monotone properties
Given a graph property Φ, the problem #IndSub(Φ) asks, on input a graph G and a positive integer k, to compute the number #IndSub(Φ, k → G) of induced subgraphs of size k in G that satisfy Φ. The search for explicit criteria on Φ ensuring that #IndSub(Φ) is hard was initiated by Jerrum and Meeks [J....
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Society for Industrial and Applied Mathematics
2022
|