Hitting forbidden induced subgraphs on bounded treewidth graphs

DOI10.1016/J.IC.2021.104812arXiv2004.08324MaRDI QIDQ6338909FDOQ6338909

Authors: Ignasi Sau, Uéverton dos Santos Souza 

Publication date: 17 April 2020

Abstract: For a fixed graph $H$, the $H$-IS-Deletion problem asks, given a graph $G$, for the minimum size of a set $SsubseteqV(G)$ such that $GsetminusS$ 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)cdot{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 $f_H(t)=2^{O(t^{h-2})}$ for every graph $H$ on $hgeq3$ vertices, and that $f_H(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 $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^{Theta(t^{h-2})}$. We also show that $f_H(t)=2^{Omega(t^h)}$ when $H=K_{h,h}$, and this reduction answers an open question of Mi. Pilipczuk [MFCS 2011] about the function $f_{C_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 $f_H(t)$ for every connected graph $H$ on $h$ vertices: if $hleq2$ the problem can be solved in polynomial time; if $hgeq3$, $f_H(t)=2^{Theta(t)}$ if $H$ is a clique, and $f_H(t)=2^{Theta(t^{h-2})}$ otherwise.

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

This page was built for publication: Hitting forbidden induced subgraphs on bounded treewidth graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6338909)