Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time

05/25/2023
by   Peter Gartland, et al.
0

We show that the Maximum Weight Independent Set problem (MWIS) can be solved in quasi-polynomial time on H-free graphs (graphs excluding a fixed graph H as an induced subgraph) for every H whose every connected component is a path or a subdivided claw (i.e., a tree with at most three leaves). This completes the dichotomy of the complexity of MWIS in ℱ-free graphs for any finite set ℱ of graphs into NP-hard cases and cases solvable in quasi-polynomial time, and corroborates the conjecture that the cases not known to be NP-hard are actually polynomial-time solvable. The key graph-theoretic ingredient in our result is as follows. Fix an integer t ≥ 1. Let S_t,t,t be the graph created from three paths on t edges by identifying one endpoint of each path into a single vertex. We show that, given a graph G, one can in polynomial time find either an induced S_t,t,t in G, or a balanced separator consisting of (log |V(G)|) vertex neighborhoods in G, or an extended strip decomposition of G (a decomposition almost as useful for recursion for MWIS as a partition into connected components) with each particle of weight multiplicatively smaller than the weight of G. This is a strengthening of a result of Majewski et al. [ICALP 2022] which provided such an extended strip decomposition only after the deletion of (log |V(G)|) vertex neighborhoods. To reach the final result, we employ an involved branching strategy that relies on the structural lemma presented above.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset