Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
复制标题
具有有界诱导循环堆积数的稀疏图具有对数树宽
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Alexandra Wesolek
中科院分区：
文献类型：
--
作者：
Marthe Bonamy;Édouard Bonnet;Hugues Déprés;Louis Esperet;Colin Geniet;Claire Hilaire;Stéphan Thomassé;Alexandra Wesolek
一个图是$mathcal{O}_k$-free的，如果它不包含$k$两两点不相交和不相邻的圈。我们证明了“稀疏”（这里，不包含大的完全二部图作为子图）$mathcal{O}_k$-free图的树宽（偶数，反馈顶点集数）至多是顶点数的对数。这是最优的，因为存在一个无限族的$mathcal{O}_2$-free图，没有$K_{2，3}$作为子图，并且其树宽（至少）是对数的。利用我们的结果，我们证明了$mathcal{O}_k$-free图的最大独立集和3-着色问题可以在拟多项式时间内求解。其他结果包括大多数中心NP完全问题（如最大独立集，最小顶点覆盖，最小支配集，最小着色）可以在稀疏$mathcal{O}_k$-free图中在多项式时间内解决，并且确定稀疏图的$mathcal{O}_k$-freeness是多项式时间可解的。
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.
登录
查看更多内容
图中没有反完全循环的诱导路径
DOI：
10.1016/j.jctb.2023.10.003
发表时间：
2024
期刊：
Journal of Combinatorial Theory, Series B
影响因子：
--
作者：
Nguyen T
通讯作者：
Nguyen T
圆盘图上最大团的 QPTAS 和次指数算法
DOI：
10.48550/arxiv.1712.05010
发表时间：
2017
期刊：
arXiv e-prints
影响因子：
--
作者：
Bonnet
通讯作者：
Bonnet
圆盘和单位球图上最大团的 EPTAS 和次指数算法
影响因子：
2.5
作者：
Bonamy M
通讯作者：
Bonamy M
归纳子图和树分解 III。
影响因子：
--
作者：
Chudnovsky, Maria;Abrishami, Tara;Hajebi, Sepehr;Spirkl, Sophie
通讯作者：
Spirkl, Sophie