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é

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)1472-1483
Number of pages12
JournalSIAM Journal on Discrete Mathematics
Volume34
Issue number2
DOIs
StatePublished - 2020

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Algorithm
  • Hole
  • Independent set
  • Perfect graph
  • Potential maximal clique
  • Stable set

Fingerprint

Dive into the research topics of 'On the maximum weight independent set problem in graphs without induced cycles of length at least five'. Together they form a unique fingerprint.

Cite this