@article{fdd9f83e5c07446dbaeace5e1b7fdbda,

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.",

keywords = "Algorithm, Hole, Independent set, Perfect graph, Potential maximal clique, Stable set",

author = "Maria Chudnovsky and Marcin Pilipczuk and Micha{\l} Pilipczuk and St{\'e}phan Thomass{\'e}",

note = "Funding Information: \ast Received by the editors March 12, 2019; accepted for publication (in revised form) May 25, 2020; published electronically June 29, 2020. https://doi.org/10.1137/19M1249473 Funding: The first author was supported by NSF grant DMS-1763817; this material is based upon work supported in part by the U. S. Army Research Office under grant W911NF-16-1-0404. The second author's research is a part of a project that has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme grant agreement 714704. The third author's research is a part of a project that has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme grant agreement 677651. \dagger Princeton University, Princeton, NJ 08544 (mchudnov@math.princeton.edu). \ddagger Institute of Informatics, University of Warsaw, Warsaw, Poland (marcin.pilipczuk@mimuw.edu. pl, michal.pilipczuk@mimuw.edu.pl). \S ENS de Lyon, 69364 Lyon Cedex 07, France (stephan.thomasse@ens-lyon.fr). Funding Information: The first author was supported by NSF grant DMS-1763817; this material is based upon work supported in part by the U. S. Army Research Office under grant W911NF-16-1-0404. The second author's research is a part of a project that has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme grant agreement 714704. The third author's research is a part of a project that has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme grant agreement 677651. Publisher Copyright: Copyright {\textcopyright} by SIAM. Unauthorized reproduction of this article is prohibited.",

year = "2020",

doi = "10.1137/19M1249473",

language = "English (US)",

volume = "34",

pages = "1472--1483",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}