2019/03/12 by Maria Chudnovsky, Chudnovsky, Maria, Marcin Pilipczuk +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithms and Data Compression #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Search Problems #cs.DM #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.1903.04761
openalex publication_date 2019/03/12 · arxiv created 2020/01/16 · arxiv updated 2020/01/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
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.