{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:13:30Z","timestamp":1759637610486,"version":"3.41.0"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,12,6]],"date-time":"2017-12-06T00:00:00Z","timestamp":1512518400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,1,31]]},"abstract":"\n In the M\n aximum<\/jats:sc>\n W\n eight<\/jats:sc>\n I\n ndependent<\/jats:sc>\n S\n et<\/jats:sc>\n problem, the input is a graph\n G<\/jats:italic>\n , every vertex has a non-negative integer weight, and the task is to find a set\n S<\/jats:italic>\n of pairwise nonadjacent vertices, maximizing the total weight of the vertices in\n S<\/jats:italic>\n . We give an\n n<\/jats:italic>\n \n O<\/jats:italic>\n (log\n 2<\/jats:sup>\n n<\/jats:italic>\n )\n <\/jats:sup>\n time algorithm for this problem on graphs excluding the path\n P<\/jats:italic>\n 6<\/jats:sub>\n on 6 vertices as an induced subgraph. Currently, there is no constant\n k<\/jats:italic>\n known for which M\n aximum<\/jats:sc>\n W\n eight<\/jats:sc>\n I\n ndependent<\/jats:sc>\n S\n et<\/jats:sc>\n on\n P<\/jats:italic>\n k<\/jats:sub>\n -free graphs becomes NP-hard, and our result implies that if such a\n k<\/jats:italic>\n exists, then\n k<\/jats:italic>\n > 6 unless all problems in NP can be decided in quasi-polynomial time.\n <\/jats:p>\n \n Using the combinatorial tools that we develop for this algorithm, we also give a polynomial-time algorithm for M\n aximum<\/jats:sc>\n W\n eight<\/jats:sc>\n E\n fficient<\/jats:sc>\n D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n on\n P<\/jats:italic>\n 6<\/jats:sub>\n -free graphs. In this problem, the input is a graph\n G<\/jats:italic>\n , every vertex has an integer weight, and the objective is to find a set\n S<\/jats:italic>\n of maximum weight such that every vertex in\n G<\/jats:italic>\n has exactly one vertex in\n S<\/jats:italic>\n in its closed neighborhood or to determine that no such set exists. Prior to our work, the class of\n P<\/jats:italic>\n 6<\/jats:sub>\n -free graphs was the only class of graphs defined by a single forbidden induced subgraph on which the computational complexity of M\n aximum<\/jats:sc>\n W\n eight<\/jats:sc>\n E\n fficient<\/jats:sc>\n D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n was unknown.\n <\/jats:p>","DOI":"10.1145\/3147214","type":"journal-article","created":{"date-parts":[[2017,12,6]],"date-time":"2017-12-06T21:23:15Z","timestamp":1512595395000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Independence and Efficient Domination on\n P<\/i>\n 6<\/sub>\n -free Graphs"],"prefix":"10.1145","volume":"14","author":[{"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[{"name":"University of Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik Jan Van","family":"Leeuwen","sequence":"additional","affiliation":[{"name":"Utrecht University, TB Utrecht, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,12,6]]},"reference":[{"volume-title":"The effect of local constraints on the complexity of determination of the graph independence number. Combinatorial-Algebraic Methods in Applied Mathematics","year":"1982","author":"Alekseev Vladimir E.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00290-1"},{"key":"e_1_2_1_3_1","volume-title":"11th International Symposium on Parameterized and Exact Computation, IPEC 2016","volume":"63","author":"Bacs\u00f3 G\u00e1bor","year":"2016"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.06.015"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(73)90042-7"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.026"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00221-X"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799359683"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2016.08.019"},{"volume-title":"Weighted efficient domination for -free graphs in polynomial time. CoRR abs\/1407.4593","year":"2014","author":"Brandst\u00e4dt Andreas","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.09.019"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.09.031"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.07.032"},{"volume-title":"- and triangle-free graphs revisited: Structure and bounded clique-width. Discrete Mathematics 8 Theoretical Computer Science 8, 1","year":"2006","author":"Brandst\u00e4dt Andreas","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40313-2_19"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00389-5"},{"volume-title":"Maximum weight independent sets for (, triangle)-free graphs in polynomial time. CoRR abs\/1511.08066","year":"2015","author":"Brandst\u00e4dt Andreas","key":"e_1_2_1_17_1"},{"volume-title":"Weighted efficient domination for -free graphs in polynomial time. CoRR abs\/1508.07733","year":"2015","author":"Brandst\u00e4dt Andreas","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1039821"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53536-3_4"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2016.06.016"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480197326346"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90002-8"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90013-5"},{"key":"e_1_2_1_25_1","unstructured":"Hendrik N. de Ridder et al. Information System on Graph Classes and Their Inclusions (ISGCI) http:\/\/www.graphclasses.org. Hendrik N. de Ridder et al. Information System on Graph Classes and Their Inclusions (ISGCI) http:\/\/www.graphclasses.org."},{"edition":"4","volume-title":"Graph Theory","author":"Diestel Reinhard","key":"e_1_2_1_26_1"},{"volume-title":"Johnson","year":"1979","author":"Garey Michael R.","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201013"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90094-X"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00395-0"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00321-3"},{"volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic Martin Charles","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"volume-title":"Polynomial-time algorithm for maximum weight independent set on -free graphs. CoRR abs\/1707.05491","year":"2017","author":"Grzesik Andrzej","key":"e_1_2_1_34_1"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2010.01.001"},{"volume-title":"Fundamentals of Domination in Graphs","author":"Haynes Teresa W.","key":"e_1_2_1_36_1"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.12.003"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Richard M. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations. 85--103. Richard M. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations. 85--103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2015.12.008"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.10.015"},{"volume-title":"Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914)","year":"2014","author":"Lokshtanov Daniel","key":"e_1_2_1_41_1"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.04.001"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2003.07.004"},{"volume-title":"Maximum weight stable set in (, bull)-free graphs. CoRR abs\/1611.09663","year":"2016","author":"Maffray Fr\u00e9d\u00e9ric","key":"e_1_2_1_44_1"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53536-3_8"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90074-X"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(96)00197-4"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00046-3"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.03.044"},{"volume-title":"Independent sets in (P6, diamond)-free graphs. Discrete Mathematics 8 Theoretical Computer Science 11, 1","year":"2009","author":"Mosca Raffaele","key":"e_1_2_1_50_1"},{"volume-title":"Some results on stable sets for k-colorable P6-free graphs and generalizations. Discrete Mathematics 8 Theoretical Computer Science 14, 2","year":"2012","author":"Mosca Raffaele","key":"e_1_2_1_51_1"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.1598"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.10.004"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2010.01.007"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90287-R"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190120313"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00138-4"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11766-004-0045-6"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3147214","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3147214","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:15Z","timestamp":1750212675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3147214"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,6]]},"references-count":58,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1,31]]}},"alternative-id":["10.1145\/3147214"],"URL":"https:\/\/doi.org\/10.1145\/3147214","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2017,12,6]]},"assertion":[{"value":"2017-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-12-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}