Quasi-polynomial-time algorithm for Independent Set in P_t-free and C_{>t}-free graphs via shrinking the space of connecting subgraphs

Prelegent(ci)

Marcin Pilipczuk

Termin

22 października 2020 12:15

Informacje na temat wydarzenia

online

Seminarium

Seminarium "Algorytmika"

---

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^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) \choose 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. 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.

---