Hitting forbidden induced subgraphs on bounded treewidth graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Information and Computation Year : 2021

Hitting forbidden induced subgraphs on bounded treewidth graphs


For a fixed graph H, the HIS Deletion problem asks, given a graph G, for the minimum size of a set S ⊆ V (G) such that G \ S does not contain H as an induced subgraph. Motivated by previous work about hitting (topological) minors and subgraphs on bounded treewidth graphs, we are interested in determining, for a fixed graph H, the smallest function fH (t) such that HIS Deletion can be solved in time fH (t) • n O(1) assuming the Exponential Time Hypothesis (ETH), where t and n denote the treewidth and the number of vertices of the input graph, respectively. We show that fH (t) = 2 O(t h−2) for every graph H on h ≥ 3 vertices, and that fH (t) = 2 O(t) if H is a clique or an independent set. We present a number of lower bounds by generalizing a reduction of Cygan et al. [Inf. Comput. 2017] for the subgraph version. In particular, we show that 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 Θ(t h−2). We also show that fH (t) = 2 Ω(t h) when H = K h,h , and this reduction answers an open question of Mi. Pilipczuk [MFCS 2011] about the function fC 4 (t) for the subgraph version. Motivated by Cygan et al. [Inf. Comput. 2017], we also consider the colorful variant of the problem, where each vertex of G is colored with some color from V (H) and we require to hit only induced copies of H with matching colors. In this case, we determine, under the ETH, the function fH (t) for every connected graph H on h vertices: if h ≤ 2 the problem can be solved in polynomial time; if h ≥ 3, fH (t) = 2 Θ(t) if H is a clique, and fH (t) = 2 Θ(t h−2) otherwise. 2012 ACM Subject Classification Theory of computation → Design and analysis of algorithms; Theory of computation → Graph algorithms analysis; Theory of computation → Parameterized complexity and exact algorithms
Fichier principal
Vignette du fichier
YINCO-D-20-00209-R1.pdf (1.07 Mo) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-03772257 , version 1 (08-09-2022)



Ignasi Sau, Uéverton dos Santos Souza. Hitting forbidden induced subgraphs on bounded treewidth graphs. Information and Computation, 2021, 281, pp.104812. ⟨10.1016/j.ic.2021.104812⟩. ⟨lirmm-03772257⟩
23 View
24 Download



Gmail Mastodon Facebook X LinkedIn More