论文标题
$ p_t $ - free图中的独立设置的准多项式时间算法，通过缩小诱导路径的空间
Quasi-polynomial-time algorithm for Independent Set in $P_t$-free graphs via shrinking the space of induced paths
论文作者
论文摘要
在最近的一项突破性工作中，Gartland和Lokshtanov [Focs 2020]显示了用于最大重量独立集的准多项式时间算法，该算法在$ p_t $ - 免费图中，也就是说，图形不包括固定路径作为诱导的子分类。他们的算法在时间上运行$ n^{\ mathcal {o}（\ log^3 n）} $，其中$ t $被认为是常数。受其想法的启发，我们可以说出一种更简单的算法，其改进的运行时间绑定为$ n^{\ Mathcal {o}（\ log^2 n）} $。我们的主要见解是，一个连接的$ p_t $ - free Graph始终包含一个顶点$ w $，其邻域相交，对于持续不断的对$ \ {u，v \} \ in \ binom {v（g）} {2} $，是诱导的$ v $ paths的恒定部分。由于$ p_t $ -free Graph包含$ \ MATHCAL {O}（n^{t-1}）$诱导的路径，总共分支在此类顶点上并在连接的组件上独立递归导致准poly-polynomial运行时间限制。我们还表明，可以使用相同的方法来获得有关相关问题的准多项式时间算法，包括最大重量诱导的匹配和3色。
In a recent breakthrough work, Gartland and Lokshtanov [FOCS 2020] showed a quasi-polynomial-time algorithm for Maximum Weight Independent Set in $P_t$-free graphs, that is, graphs excluding a fixed path as an induced subgraph. Their algorithm runs in time $n^{\mathcal{O}(\log^3 n)}$, where $t$ is assumed to be a constant. Inspired by their ideas, we present an arguably simpler algorithm with an improved running time bound of $n^{\mathcal{O}(\log^2 n)}$. Our main insight is that a connected $P_t$-free graph always contains a vertex $w$ whose neighborhood intersects, for a constant fraction of pairs $\{u,v\} \in \binom{V(G)}{2}$, a constant fraction of induced $u-v$ paths. Since a $P_t$-free graph contains $\mathcal{O}(n^{t-1})$ induced paths in total, branching on such a vertex and recursing independently on the connected components leads to a quasi-polynomial running time bound. We also show that the same approach can be used to obtain quasi-polynomial-time algorithms for related problems, including Maximum Weight Induced Matching and 3-Coloring.
