3618260.3649644.pdf (256.48 kB)

# Counting Small Induced Subgraphs with Edge-Monotone Properties

conference contribution

posted on 2024-06-26, 07:26 authored by Simon Döring, Dániel MarxDániel Marx, Philip WellnitzWe study the parameterized complexity of #IndSub(Φ), where given a graph G and an integer k, the task is to count the number of induced subgraphs on k vertices that satisfy the graph property Φ. Focke and Roth [STOC 2022] completely characterized the complexity for each Φ that is a hereditary property (that is, closed under vertex deletions): #IndSub(Φ) is #W[1]-hard except in the degenerate cases when every graph satisfies Φ or only finitely many graphs satisfy Φ. We complement this result with a classification for each Φ that is edge-monotone (that is, closed under edge deletions): #IndSub(Φ) is #W[1]-hard except in the degenerate case when there are only finitely many integers k such that Φ is nontrivial on k-vertex graphs. Our result generalizes earlier results for specific properties Φ that are related to the connectivity or density of the graph. Further, we extend the #W[1]-hardness result by a lower bound which shows that #IndSub(Φ) cannot be solved in time f(k) · |V(G)|o(√logk / loglogk) for any function f, unless the Exponential-Time Hypothesis (ETH) fails. For many natural properties, we obtain even a tight bound f(k) · |V(G)|o(k); for example, this is the case for every property Φ that is nontrivial on k-vertex graphs for each k greater than some k0.

## History

## Primary Research Area

- Algorithmic Foundations and Cryptography

## Name of Conference

ACM Symposium on Theory of Computing (STOC)## Page Range

1517-1525## Publisher

Association for Computing Machinery (ACM)## Open Access Type

- Unknown

## BibTeX

@conference{Döring:Marx:Wellnitz:2024, title = "Counting Small Induced Subgraphs with Edge-Monotone Properties", author = "Döring, Simon" AND "Marx, Dániel" AND "Wellnitz, Philip", year = 2024, month = 6, pages = "1517--1525", publisher = "Association for Computing Machinery (ACM)", doi = "10.1145/3618260.3649644" }## Usage metrics

## Categories

No categories selected## Keywords

## Licence

## Exports

RefWorks

BibTeX

Ref. manager

Endnote

DataCite

NLM

DC