Paper Info
Title
On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five.
Abstract
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.
Year
DOI
Venue
2020
10.1137/19M1249473
SIAM JOURNAL ON DISCRETE MATHEMATICS
Keywords
DocType
Volume
stable set,independent set,hole,perfect graph,algorithm,potential maximal clique
Journal
34
Issue
ISSN
Citations 
2
0895-4801
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Maria Chudnovsky139046.13
Marcin Pilipczuk243647.86
michal pilipczuk340351.93
Stéphan Thomassé465166.03