论文标题
稀疏的图形诱导周期堆积数具有对数树宽
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
论文作者
论文摘要
图形为$ \ Mathcal {o} _k $ - 如果不包含$ K $ pairwise pertex-disjoint和非Adjacent Cycles，则图形是图形。我们证明“稀疏”（在这里，不包含大型完整的两部分图形作为子图）$ \ Mathcal {o} _k $ - Free Graphs在最多的位置上都具有treewidth（甚至最多，反馈顶点集号码）。这是最佳的，因为$ \ Mathcal {o} _2 $ - free图的无限家族，而没有$ k_ {2,3} $作为子图，而其treewidth是（至少）对数。 使用我们的结果，我们表明，可以在quasi-polynomial时间时间求解最大独立集和3色。 Other consequences include that most of the central NP-complete problems (such as Maximum Independent Set, Minimum Vertex Cover, Minimum Dominating Set, Minimum Coloring) can be solved in polynomial time in sparse $\mathcal{O}_k$-free graphs, and that deciding the $\mathcal{O}_k$-freeness of sparse graphs is polynomial time solvable.
A graph is $\mathcal{O}_k$-free if it does not contain $k$ pairwise vertex-disjoint and non-adjacent cycles. We prove that "sparse" (here, not containing large complete bipartite graphs as subgraphs) $\mathcal{O}_k$-free graphs have treewidth (even, feedback vertex set number) at most logarithmic in the number of vertices. This is optimal, as there is an infinite family of $\mathcal{O}_2$-free graphs without $K_{2,3}$ as a subgraph and whose treewidth is (at least) logarithmic. Using our result, we show that Maximum Independent Set and 3-Coloring in $\mathcal{O}_k$-free graphs can be solved in quasi-polynomial time. Other consequences include that most of the central NP-complete problems (such as Maximum Independent Set, Minimum Vertex Cover, Minimum Dominating Set, Minimum Coloring) can be solved in polynomial time in sparse $\mathcal{O}_k$-free graphs, and that deciding the $\mathcal{O}_k$-freeness of sparse graphs is polynomial time solvable.
