2026-08-12T00:10:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12751 2024-03-06T10:50:44Z ddc:004 open_access

Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs Sau, Ignasi Souza, Uéverton dos Santos parameterized complexity induced subgraphs treewidth hitting subgraphs dynamic programming lower bound Exponential Time Hypothesis 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 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 f_H(t) such that H-IS-Deletion can be solved in time f_H(t) ⋅ n^{𝒪(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 f_H(t) = 2^{𝒪(t^{h-2})} for every graph H on h ≥ 3 vertices, and that f_H(t) = 2^{𝒪(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 f_H(t) suffers a sharp jump: if H is obtained from a clique of size h by removing one edge, then f_H(t) = 2^{Θ(t^{h-2})}. We also show that f_H(t) = 2^{Ω(t^{h})} when H = K_{h,h}, and this reduction answers an open question of Mi. Pilipczuk [MFCS 2011] about the function f_{C₄}(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 f_H(t) for every connected graph H on h vertices: if h ≤ 2 the problem can be solved in polynomial time; if h ≥ 3, f_H(t) = 2^{Θ(t)} if H is a clique, and f_H(t) = 2^{Θ(t^{h-2})} otherwise. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ignasi Sau and Uéverton dos Santos Souza 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.82 urn:nbn:de:0030-drops-127511 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.82 eng https://creativecommons.org/licenses/by/3.0/legalcode