In a recent  work, Gartland and Lokshtanov [FOCS 2020] gave a quasi-polynomial-time algorithm for Maximum Weight Independent Set in P_t-free graphs, that is, graphs excluding a path on t vertices as an induced subgraph. Their algorithm runs in time n^{ 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^{ 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 V(G){2}, a constant fraction of induced u-v paths. Since a P_t-free graph contains 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. In a subsequent and very recent work, Gartland and Lokshtanov arXiv:2007.11402%DIFDELCMD < ] %%% extended their ideas to C_{> t-free graphs: graphs that do not contain a cycle on more than t vertices as an induced subgraph. They obtained an algorithm for Maximum Weight Independent Set in this graph class with running time n^{O(\log^5 n)}. We show that it is possible to combine their ideas with our new understanding, and thus obtain an algorithm that runs in time n^{O(\log^4 n)}. We also show how to use }  the same approach  to obtain quasi-polynomial-time algorithms for related problems, including Maximum Weight Induced Matching and 3-Coloring , in P_t-free and C_{>t .
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 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. %DIFDELCMD < ] %%% -free graphs: graphs that do not contain a cycle on more than t vertices as an induced subgraph. They obtained an algorithm for Maximum Weight Independent Set in this graph class with running time n^{O(\log^5 n)}. We show that it is possible to combine their ideas with our new understanding, and thus obtain an algorithm that runs in time n^{O(\log^4 n)}. We also show how to use } 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 .
A
breakthrough
R
gave
showed
R
path on t vertices
fixed path
R
O
\mathcal{O
D
~
R
O
\mathcal{O
R
O
\mathcal{O
D
In a subsequent and very recent work, Gartland and Lokshtanov
D
arXiv:2007.11402
D
extended their ideas to C_{> t
A
We also show that
A
can be used
D
, in P_t-free and C_{>t