Hitting forbidden induced subgraphs on bounded treewidth graphs

For a fixed graph H, the H-IS-Deletion problem asks, given a graph G, for the minimum size of a set S⊆V(G) such that G∖S excludes H as an induced subgraph. We are interested in determining, for a fixed H, the smallest function fH(t) such that H-IS-Deletion can be solved in time fH(t)⋅nO(1) assuming...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2021-12, Vol.281, p.104812, Article 104812
Main Authors: Sau, Ignasi, dos Santos Souza, Uéverton
Format: Article
Language:English
Subjects:
Dynamic programming
Exponential time hypothesis
Hitting subgraphs
Induced subgraphs
Lower bound
Mathematics
Parameterized complexity
Treewidth
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:For a fixed graph H, the H-IS-Deletion problem asks, given a graph G, for the minimum size of a set S⊆V(G) such that G∖S excludes H as an induced subgraph. We are interested in determining, for a fixed H, the smallest function fH(t) such that H-IS-Deletion can be solved in time fH(t)⋅nO(1) assuming the Exponential Time Hypothesis, where t and n denote the treewidth and the number of vertices of G, respectively. We show that fH(t)=2O(th−2) for every H on h≥3 vertices, and that fH(t)=2O(t) if H is a clique or an independent set. When H deviates slightly from a clique, the function fH(t) suffers a sharp jump: if H is obtained from a clique of size h by removing one edge, then fH(t)=2Θ(th−2). Moreover, fH(t)=2Ω(th) when H=Kh,h, answering a question of Pilipczuk [MFCS 2011].
ISSN:0890-5401
1090-2651
DOI:10.1016/j.ic.2021.104812