CISPA
Browse
3618260.3649644.pdf (256.48 kB)

Counting Small Induced Subgraphs with Edge-Monotone Properties

Download (256.48 kB)
conference contribution
posted on 2024-06-26, 07:26 authored by Simon Döring, Dániel MarxDániel Marx, Philip Wellnitz
We 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

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC