论文标题
有界树宽和容器方法的诱导子图
Induced subgraphs of bounded treewidth and the container method
论文作者
论文摘要
图中的一个孔是一个至少4个长度的诱导循环。如果其长度至少为5。孔长度很长。$ p_t $，我们表示$ t $ dertices的路径。在本文中，我们为以下问题提供了多项式时间算法：无孔图中的最大权重设置问题，而反馈顶点集问题$ p_5 $ free-free Graphs。上述每个结果都解决了相应的长期开放问题。 扩展的$ C_5 $是一个五个vertex孔，该孔连续一个或两个连续的顶点附近。令$ \ mathcal {c} $为图形类别，不包括扩展的$ C_5 $和长度至少$ 6 $的孔，如诱导的子图； $ \ mathcal {c} $包含所有无长孔图和所有$ p_5 $ - free图。我们表明，考虑到带有顶点权重和整数$ k $的$ n $ vertex图$ g \ in \ mathcal {c} $，一个人可以$ n^{\ oh（k）} $找到一个最大降低诱导的$ g $ g $ g $ g $ g $ g $ g $ g $ g $ g y lyt bed $ k $。这意味着两个结果。
A hole in a graph is an induced cycle of length at least 4. A hole is long if its length is at least 5. By $P_t$ we denote a path on $t$ vertices. In this paper we give polynomial-time algorithms for the following problems: the Maximum Weight Independent Set problem in long-hole-free graphs, and the Feedback Vertex Set problem in $P_5$-free graphs. Each of the above results resolves a corresponding long-standing open problem. An extended $C_5$ is a five-vertex hole with an additional vertex adjacent to one or two consecutive vertices of the hole. Let $\mathcal{C}$ be the class of graphs excluding an extended $C_5$ and holes of length at least $6$ as induced subgraphs; $\mathcal{C}$ contains all long-hole-free graphs and all $P_5$-free graphs. We show that, given an $n$-vertex graph $G \in \mathcal{C}$ with vertex weights and an integer $k$, one can in time $n^{\Oh(k)}$ find a maximum-weight induced subgraph of $G$ of treewidth less than $k$. This implies both aforementioned results.
