{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T03:22:20Z","timestamp":1790738540733,"version":"4.1.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,1,23]],"date-time":"2022-01-23T00:00:00Z","timestamp":1642896000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["UMO-2013\/09\/B\/ST6\/03136.Mi"],"award-info":[{"award-number":["UMO-2013\/09\/B\/ST6\/03136.Mi"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Foundation for Polish Science (FNP) via the START stipend programme"},{"name":"European Research Council (ERC) under the European Union\u2019s Horizon 2020 research and innovation programme","award":["714704 and 677651"],"award-info":[{"award-number":["714704 and 677651"]}]},{"name":"ANR project Stint","award":["ANR-13-BS02-0007"],"award-info":[{"award-number":["ANR-13-BS02-0007"]}]},{"name":"LABEX MILYON","award":["ANR-10-LABX-0070"],"award-info":[{"award-number":["ANR-10-LABX-0070"]}]},{"name":"\u201cInvestissements d\u2019Avenir\u201d","award":["ANR-11-IDEX-0007"],"award-info":[{"award-number":["ANR-11-IDEX-0007"]}]},{"name":"French National Research Agency (ANR), by Center of Excellence \u2013 ITI","award":["P202\/12\/G061"],"award-info":[{"award-number":["P202\/12\/G061"]}]},{"name":"Center for Foundations of Modern Computer Science","award":["UNCE\/SCI\/004"],"award-info":[{"award-number":["UNCE\/SCI\/004"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,1,31]]},"abstract":"<jats:p>\n            In the classic\n            <jats:sc>Maximum Weight Independent Set<\/jats:sc>\n            problem, we are given a graph\n            <jats:italic>G<\/jats:italic>\n            with a nonnegative weight function on its vertices, and the goal is to find an independent set in\n            <jats:italic>G<\/jats:italic>\n            of maximum possible weight. While the problem is NP-hard in general, we give a polynomial-time algorithm working on any\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>6<\/jats:sub>\n            -free graph, that is, a graph that has no path on 6 vertices as an induced subgraph. This improves the polynomial-time algorithm on\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>5<\/jats:sub>\n            -free graphs of Lokshtanov et al. [\n            <jats:xref ref-type=\"bibr\">15<\/jats:xref>\n            ] and the quasipolynomial-time algorithm on\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>6<\/jats:sub>\n            -free graphs of Lokshtanov et al. [\n            <jats:xref ref-type=\"bibr\">14<\/jats:xref>\n            ]. The main technical contribution leading to our main result is enumeration of a polynomial-size family \u2131 of vertex subsets with the following property: For every maximal independent set\n            <jats:italic>I<\/jats:italic>\n            in the graph, \u2131 contains all maximal cliques of some minimal chordal completion of\n            <jats:italic>G<\/jats:italic>\n            that does not add any edge incident to a vertex of\n            <jats:italic>I<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3414473","type":"journal-article","created":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T05:51:05Z","timestamp":1643003465000},"page":"1-57","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["Polynomial-time Algorithm\u00a0for Maximum Weight Independent Set on\n            <i>P<\/i>\n            <sub>6<\/sub>\n            -free Graphs"],"prefix":"10.1145","volume":"18","author":[{"given":"Andrzej","family":"Grzesik","sequence":"first","affiliation":[{"name":"Faculty of Mathematics and Computer Science, Jagiellonian University, Krak\u00f3w, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tereza","family":"Klimo\u0161ov\u00e1","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics, Charles University, Praha, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warszawa, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warszawa, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,1,23]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"68th Polish Mathematical Olympiad. 2017. Solutions to the Second Round Problems. (2017). Polish version with solutions available at https:\/\/om.mimuw.edu.pl\/static\/app_main\/problems\/om68_2r.pdf. English translation of the problem statements available at https:\/\/artofproblemsolving.com\/community\/c416662_2017_second_round__poland."},{"key":"e_1_3_2_3_2","unstructured":"Vladimir E. Alekseev. 1982. The effect of local constraints on the complexity of determination of the graph independence number. Combinatorial-Algebraic Methods in Applied Mathematics. Gorkiy University Press Gorky. 3\u201313. (in Russian)."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799359683"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00007-X"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2018.11.005"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90013-5"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02992776"},{"key":"e_1_3_2_9_2","first-page":"383","volume-title":"STACS (LIPIcs)","author":"Fomin Fedor V.","year":"2010","unstructured":"Fedor V. Fomin and Yngve Villanger. 2010. Finding induced subgraphs via minimal triangulations. In STACS (LIPIcs), Vol. 5. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 383\u2013394."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020961"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310512"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2010.01.001"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3147214"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634117"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.04.001"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90074-X"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.5555\/646249.685341"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(82)90047-8"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90287-R"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3414473","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3414473","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:38Z","timestamp":1750199918000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3414473"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,23]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1,31]]}},"alternative-id":["10.1145\/3414473"],"URL":"https:\/\/doi.org\/10.1145\/3414473","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,23]]},"assertion":[{"value":"2019-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}