{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:45:54Z","timestamp":1787323554984,"version":"build-2736575974"},"reference-count":13,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-16-1-0404"],"award-info":[{"award-number":["W911NF-16-1-0404"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["714704"],"award-info":[{"award-number":["714704"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["677651"],"award-info":[{"award-number":["677651"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1763817"],"award-info":[{"award-number":["DMS-1763817"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/19m1249473","type":"journal-article","created":{"date-parts":[[2020,6,29]],"date-time":"2020-06-29T14:47:40Z","timestamp":1593442060000},"page":"1472-1483","source":"Crossref","is-referenced-by-count":13,"title":["On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five"],"prefix":"10.1137","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8920-4944","authenticated-orcid":true,"given":"Maria","family":"Chudnovsky","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"St\u00e9phan","family":"Thomass\u00e9","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,6,29]]},"reference":[{"key":"atypb1","unstructured":"T. Abrishami, M. Chudnovsky, and M. Pilipczuk,\n                      Containers for Minimal Separators in Graphs with No Holes of Length at Least Five\n                      , manuscript in preparation, 2019."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0479-5"},{"key":"atypb3","first-page":"123","volume":"9","author":"Berge C.","year":"1960","journal-title":"Publ. Inst. Stat. Univ. Paris"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799359683"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00007-X"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0012-8"},{"key":"atypb7","first-page":"2260","author":"Chudnovsky M.","year":"2020","journal-title":"SIAM"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2006.164.51"},{"key":"atypb9","unstructured":"P. Gartland and D. Lokshtanov,\n                      Independent Set on ${P}_k$-Free Graphs in Quasi-Polynomial Time\n                      , e-print, CoRR, abs\/2005.00690 (2020),https:\/\/arxiv.org\/abs\/2005.00690."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2019.04.010"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"atypb12","first-page":"1257","author":"Grzesik A.","year":"2019","journal-title":"SIAM"},{"key":"atypb13","first-page":"570","author":"Lokshtanov D.","year":"2014","journal-title":"SIAM"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1249473","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:09:01Z","timestamp":1787321341000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1249473"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/19M1249473"],"URL":"https:\/\/doi.org\/10.1137\/19m1249473","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}