Skip to Main content Skip to Navigation
Conference papers

Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs

Ignasi Sau Valls 1 Uéverton dos Santos Souza 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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. [MFCS 2014] 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. [MFCS 2014], 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download
Contributor : Isabelle Gouat <>
Submitted on : Friday, November 6, 2020 - 10:57:50 AM
Last modification on : Monday, December 14, 2020 - 5:27:16 PM
Long-term archiving on: : Sunday, February 7, 2021 - 6:35:10 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License




Ignasi Sau Valls, Uéverton dos Santos Souza. Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs. 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), Aug 2020, Prague, Czech Republic. pp.82:1-82:15, ⟨10.4230/LIPIcs.MFCS.2020.82⟩. ⟨lirmm-02991913⟩



Record views


Files downloads