***********************************
* Princeton Discrete Math Seminar *
***********************************
Speaker: Peter Gartland (UC Santa Barbara)
Thursday 7th September, 3:00 in Fine Hall 224.
Maximum weight independent set in graphs with no long claws in
quasi-polynomial time
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 F-free
graphs for any finite set F 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.
----------------------------------
Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)