Tree independence number II. Three-path-configurations
arxiv(2024)
摘要
A three-paths-configuration is a graph consisting of three pairwise
internally-disjoint paths the union of every two of which is an induced cycle
of length at least four. A graph is 3PC-free if no induced subgraph of
it is a three-paths-configuration. We prove that 3PC-free graphs have
poly-logarithmic tree-independence number. More explicitly, we show that there
exists a constant c such that every n-vertex 3PC-free graph graph has a
tree decomposition in which every bag has stability number at most c (log
n)^2. This implies that the Maximum Weight Independent Set problem,
as well as several other natural algorithmic problems, that are known to be
-hard in general, can be solved in quasi-polynomial time if the
input graph is 3PC-free.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要