论文标题
在有限的树宽图上击中禁止的诱导子图
Hitting forbidden induced subgraphs on bounded treewidth graphs
论文作者
论文摘要
对于固定的图形$ h $，给定图形$ g $的$ h $ is-is-depterion问题，对于集合$ s \ subseteq v（g）$的最小尺寸，以至于$ g \ setminus s $不包含$ h $作为诱导子级的$ h $。 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分别是树宽和输入图的顶点的数量。 我们表明，$ f_h（t）= 2^{o（t^{h-2}）} $对于$ h \ geq 3 $ vertices上的每个图$ h $，而$ f_h（t）= 2^{o（t）$ h $是$ h $，如果$ h $是一个集团或独立集。我们通过概括Cygan等人的概括来提供许多下限。 [MFCS 2014]对于子图版本。特别是，我们表明，当$ h $与一个集团略微偏离时，功能$ f_h（t）$会急剧跳跃：如果$ h $是通过删除一个边缘从$ h $的集团获得的$ h $，则$ f_h（t）= 2^{θ{θ（t^{h-2}）} $。我们还表明，当$ h = k_ {h，h} $时，$ f_h（t）= 2^{ω（t^{h}）} $，此简化回答了mi的开放问题。 Pilipczuk [MFCS 2011]关于子图版本的功能$ f_ {c_4}（t）$。 由Cygan等人动机。 [MFCS 2014]，我们还考虑了该问题的五颜六色变体，其中$ g $的每个顶点均以$ v（h）$中的某些颜色颜色，我们只需要达到带有匹配颜色的$ h $的感应副本。在这种情况下，我们根据ETH确定$ h $ vertices上每个连接的图形$ h $的函数$ f_h（t）$：如果$ h \ leq 2 $ 2 $，则可以在多项式时间内解决问题；如果$ h \ geq 3 $，$ f_h（t）= 2^{θ（t）} $如果$ h $是一个集团，而$ f_h（t）= 2^{θ（t^{h-2}）} $否则。
For a fixed graph $H$, the $H$-IS-Deletion problem asks, given a graph $G$, for the minimum size of a set $S \subseteq V(G)$ such that $G\setminus 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) \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 $h \geq 3$ 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^{Θ(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_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 $h\leq 2$ the problem can be solved in polynomial time; if $h\geq 3$, $f_H(t) = 2^{Θ(t)}$ if $H$ is a clique, and $f_H(t) = 2^{Θ(t^{h-2})}$ otherwise.
