License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.82
URN: urn:nbn:de:0030-drops-127511
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12751/
Sau, Ignasi ;
Souza, Uéverton dos Santos
Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs
Abstract
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.
BibTeX - Entry
@InProceedings{sau_et_al:LIPIcs:2020:12751,
author = {Ignasi Sau and U{\'e}verton dos Santos Souza},
title = {{Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {82:1--82:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-159-7},
ISSN = {1868-8969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12751},
URN = {urn:nbn:de:0030-drops-127511},
doi = {10.4230/LIPIcs.MFCS.2020.82},
annote = {Keywords: parameterized complexity, induced subgraphs, treewidth, hitting subgraphs, dynamic programming, lower bound, Exponential Time Hypothesis}
}
|
Keywords: |
|
parameterized complexity, induced subgraphs, treewidth, hitting subgraphs, dynamic programming, lower bound, Exponential Time Hypothesis |
|
Collection: |
|
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
18.08.2020 |
