On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five
Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, Stéphan Thomassé · SIAM Journal on Discrete Mathematics · 2020
A hole in a graph is an induced cycle of length at least 4, and an antihole is the complement of an induced cycle of length at least 4. A hole or antihole is long if its length is at least 5. For an integer $k$, the $k$-prism is the graph consisting of two cliques of size $k$ joined by a matching. The complexity of Maximum (Weight) Independent Set (MWIS) in long-hole-free graphs remains an important open problem. In this paper we give a polynomial-time algorithm to solve MWIS in long-hole-free graphs with no $k$-prism (for any fixed integer $k$) and a subexponential algorithm for MWIS in long-hole-free graphs in general. As a special case this gives a polynomial-time algorithm to find a maximum weight clique in perfect graphs with no long antihole and no hole of length 6. The algorithms use the framework of minimal chordal completions and potential maximal cliques.