论文标题
p $ _k $ - quasi-polynomial时间的独立集
Independent Set on P$_k$-Free Graphs in Quasi-Polynomial Time
论文作者
论文摘要
我们提出了一种算法，该算法将其作为输入$ g $，并在顶点上具有权重，并计算最大权重独立集$ s $ $ g $。如果输入图$ g $将$ k $ Vertices上的路径$ p_k $作为诱导子图，则该算法在时间$ n^{o（k^2 \ log^3 n）} $中运行。因此，对于我们的算法，每一个固定的$ k $都以准多项式时间运行。这在肯定的[thomassé，Soda'20被邀请演讲]的肯定问题中解决。在此工作之前，多项式时间算法仅以$ p_4 $ -free图[Corneil等，Dam'81]，$ P_5 $ - Free Graphs [Lokshtanov等，Soda'14]和$ P_6 $ - FREE GRAPHS [GRZESIK等[GRZESIK等人，Soda'19]]。对于$ t $的较大值，只有$ 2^{o（\ sqrt {kn \ log n}）} $ time算法[Bascó等，algorithmica'19]和quasi-pysolimial ialial时间近似近似方案[Chudnovsky等人[Chudnovsky et al。，Soda'20]已知。因此，我们的工作是第一个提供结论性证据的工作，即$ P_K $ free图上的独立设置对于任何整数$ k $而言均不符合NP的完整。 此外，我们证明，对于每个图$ h $，如果存在$ c $ - free Graphs on py-poly-poly-poly-poly-poly-polynomial time算法，则对于每个连接的组件$ c $ $ h $的$ c $ - free图，则在$ h $ free h $ h $ -free Grables上{\ sc ippertional in Ipplants py secters age py y h $ $ h $ a $ $ h $ a $。这将我们的准多项式时间算法提升到$ t_k $ - free图，其中$ t_k $具有一个$ p_k $的组件，而$ k-1 $组成部分是fork to for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for $ 3 $ 3 $ $ 3 $ $ 3 $ $ 3 $ $ 3 $ $ 3 $ $ 3。
We present an algorithm that takes as input a graph $G$ with weights on the vertices, and computes a maximum weight independent set $S$ of $G$. If the input graph $G$ excludes a path $P_k$ on $k$ vertices as an induced subgraph, the algorithm runs in time $n^{O(k^2 \log^3 n)}$. Hence, for every fixed $k$ our algorithm runs in quasi-polynomial time. This resolves in the affirmative an open problem of [Thomassé, SODA'20 invited presentation]. Previous to this work, polynomial time algorithms were only known for $P_4$-free graphs [Corneil et al., DAM'81], $P_5$-free graphs [Lokshtanov et al., SODA'14], and $P_6$-free graphs [Grzesik et al., SODA'19]. For larger values of $t$, only $2^{O(\sqrt{kn\log n})}$ time algorithms [Bascó et al., Algorithmica'19] and quasi-polynomial time approximation schemes [Chudnovsky et al., SODA'20] were known. Thus, our work is the first to offer conclusive evidence that Independent Set on $P_k$-free graphs is not NP-complete for any integer $k$. Additionally we show that for every graph $H$, if there exists a quasi-polynomial time algorithm for Independent Set on $C$-free graphs for every connected component $C$ of $H$, then there also exists a quasi-polynomial time algorithm for {\sc Independent Set} on $H$-free graphs. This lifts our quasi-polynomial time algorithm to $T_k$-free graphs, where $T_k$ has one component that is a $P_k$, and $k-1$ components isomorphic to a fork (the unique $5$-vertex tree with a degree $3$ vertex).
