文章基本信息

标题：Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs
本地全文：下载
作者：Ignasi Sau ; Uverton dos Santos Souza
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：170
页码：82:1-82:15
DOI：10.4230/LIPIcs.MFCS.2020.82
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：For a fixed graph H, the H-IS-Deletion problem asks, given a graph G, for the minimum size of a set S â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.
关键词：parameterized complexity; induced subgraphs; treewidth; hitting subgraphs; dynamic programming; lower bound; Exponential Time Hypothesis