{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T10:53:19Z","timestamp":1725792799192},"reference-count":81,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,4,22]],"date-time":"2019-04-22T00:00:00Z","timestamp":1555891200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/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":[[2019,4,30]]},"abstract":"\n We algorithmize the structural characterization for claw-free graphs by Chudnovsky and Seymour. Building on this result, we show that D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n on claw-free graphs is (i) fixed-parameter tractable and (ii) even possesses a polynomial kernel. To complement these results, we establish that D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n is unlikely to be fixed-parameter tractable on the slightly larger class of graphs that exclude\n K<\/jats:italic>\n 1,4<\/jats:sub>\n as an induced subgraph (\n K<\/jats:italic>\n 1,4<\/jats:sub>\n -free graphs). We show that our algorithmization can also be used to show that the related C\n onnected<\/jats:sc>\n D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n problem is fixed-parameter tractable on claw-free graphs. To complement that result, we show that C\n onnected<\/jats:sc>\n D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n is unlikely to have a polynomial kernel on claw-free graphs and is unlikely to be fixed-parameter tractable on\n K<\/jats:italic>\n 1,4<\/jats:sub>\n -free graphs. Combined, our results provide a dichotomy for D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n and C\n onnected<\/jats:sc>\n D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n on\n K<\/jats:italic>\n 1,\u2113<\/jats:sub>\n -free graphs and show that the problem is fixed-parameter tractable if and only if \u2113 \u2264 3.\n <\/jats:p>","DOI":"10.1145\/3301445","type":"journal-article","created":{"date-parts":[[2019,4,23]],"date-time":"2019-04-23T15:24:23Z","timestamp":1556033063000},"page":"1-90","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Domination When the Stars Are Out"],"prefix":"10.1145","volume":"15","author":[{"given":"Danny","family":"Hermelin","sequence":"first","affiliation":[{"name":"Ben-Gurion University of the Negev, Beer-Sheva, Israel"}]},{"given":"Matthias","family":"Mnich","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Bonn and Maastricht University, Maastricht, The Netherlands"}]},{"given":"Erik Jan Van","family":"Leeuwen","sequence":"additional","affiliation":[{"name":"Utrecht University, The Netherlands"}]},{"given":"Gerhard","family":"Woeginger","sequence":"additional","affiliation":[{"name":"RWTH Aachen, Aachen, Germany"}]}],"member":"320","published-online":{"date-parts":[[2019,4,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90105-X"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250801"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792238431"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/10080052X"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2012.11.003"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.07.003"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1776096.1776097"},{"key":"e_1_2_1_8_1","unstructured":"M. Chudnovsky and A. D. King. 2011. Optimal antithickenings of claw-free trigraphs. arXiv:1110.5111. M. Chudnovsky and A. D. King. 2011. Optimal antithickenings of claw-free trigraphs. arXiv:1110.5111."},{"key":"e_1_2_1_9_1","first-page":"153","article-title":"The structure of claw-free graphs","volume":"327","author":"Chudnovsky M.","year":"2005","unstructured":"M. Chudnovsky and P. D. Seymour . 2005 . The structure of claw-free graphs . London Mathematical Society Lecture Note Series: Surveys in Combinatorics 327 (2005), 153 -- 171 . M. Chudnovsky and P. D. Seymour. 2005. The structure of claw-free graphs. London Mathematical Society Lecture Note Series: Surveys in Combinatorics 327 (2005), 153--171.","journal-title":"London Mathematical Society Lecture Note Series: Surveys in Combinatorics"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.02.002"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.06.006"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.03.001"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.06.007"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.03.002"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2010.04.005"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.07.005"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1385429.1385433"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31155-0_9"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"M. Cygan F. V. Fomin \u0141. Kowalik D. Lokshtanov D. Marx M. Pilipczuk M. Pilipczuk and S. Saurabh. 2015. Parameterized Algorithms. Springer. M. Cygan F. V. Fomin \u0141. Kowalik D. Lokshtanov D. Marx M. Pilipczuk M. Pilipczuk and S. Saurabh. 2015. Parameterized Algorithms. Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.09.010"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(85)80001-7"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1090"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.004"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792269095"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_32"},{"key":"e_1_2_1_26_1","volume-title":"Congressus Numerantium 87","author":"Downey R. G.","year":"1992","unstructured":"R. G. Downey and M. R. Fellows . 1992. Fixed-parameter tractability and completeness . Congressus Numerantium 87 ( 1992 ), 161--178. R. G. Downey and M. R. Fellows. 1992. Fixed-parameter tractability and completeness. Congressus Numerantium 87 (1992), 161--178."},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Springer New York. R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Springer New York.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows. 2013. Fundamentals of Parameterized Complexity Theory. Springer. R. G. Downey and M. R. Fellows. 2013. Fundamentals of Parameterized Complexity Theory. Springer.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2244-x"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629600"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2011.04.002"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(96)00045-3"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.09.065"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/11847250_13"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"F. V. Fomin and D. Kratsch. 2010. Exact Exponential Algorithms. Texts in Theoretical Computer Science Springer. F. V. Fomin and D. Kratsch. 2010. Exact Exponential Algorithms. Texts in Theoretical Computer Science Springer.","DOI":"10.1007\/978-3-642-16533-7"},{"key":"e_1_2_1_38_1","unstructured":"J. Flum and M. Grohe. 2006. Parameterized Complexity Theory. Springer. J. Flum and M. Grohe. 2006. Parameterized Complexity Theory. Springer."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2010.05.130"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/0132071"},{"key":"e_1_2_1_41_1","unstructured":"M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company. M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/140963200"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009201"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00241-7"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the STACS, M. Morvan, C. Meinel, and D. Krob (Eds.), LNCS 1373","author":"Habib M.","unstructured":"M. Habib , C. Paul , and L. Viennot . 1998. A synthesis on partition refinement: A useful routine for strings, graphs, boolean matrices and automata . In Proceedings of the STACS, M. Morvan, C. Meinel, and D. Krob (Eds.), LNCS 1373 . Springer-Verlag, Berlin, 25--38. M. Habib, C. Paul, and L. Viennot. 1998. A synthesis on partition refinement: A useful routine for strings, graphs, boolean matrices and automata. In Proceedings of the STACS, M. Morvan, C. Meinel, and D. Krob (Eds.), LNCS 1373. Springer-Verlag, Berlin, 25--38."},{"key":"e_1_2_1_46_1","unstructured":"T. W. Haynes S. T. Hedetniemi and P. J. Slater. 1998. Fundamentals of Domination in Graphs. Marcel Dekker Inc. New York. T. W. Haynes S. T. Hedetniemi and P. J. Slater. 1998. Fundamentals of Domination in Graphs. Marcel Dekker Inc. New York."},{"key":"e_1_2_1_47_1","volume-title":"Graphs: Advanced Topics","author":"Haynes T. W.","year":"1998","unstructured":"T. W. Haynes , S. T. Hedetniemi , and P. J. Slater . 1998 . Domination in Graphs: Advanced Topics . Marcel Dekker Inc., New York . T. W. Haynes, S. T. Hedetniemi, and P. J. Slater. 1998. Domination in Graphs: Advanced Topics. Marcel Dekker Inc., New York."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9877-5"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90165-E"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/0207033"},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the WALCOM, M. Sohel Rahman and E. Tomita (Eds.), LNCS 8973","author":"Iwaide K.","unstructured":"K. Iwaide and H. Nagamochi . 2015. An improved algorithm for parameterized edge dominating set problem . In Proceedings of the WALCOM, M. Sohel Rahman and E. Tomita (Eds.), LNCS 8973 . Springer-Verlag, Berlin, 234--245. K. Iwaide and H. Nagamochi. 2015. An improved algorithm for parameterized edge dominating set problem. In Proceedings of the WALCOM, M. Sohel Rahman and E. Tomita (Eds.), LNCS 8973. Springer-Verlag, Berlin, 234--245."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"e_1_2_1_54_1","volume-title":"Complexity of Computer Computations","author":"Karp R. M.","unstructured":"R. M. Karp . {n.d.}. Reducibility among combinatorial problems . In Complexity of Computer Computations , R. E. Miller and J. W. Thatcher (Eds.). Plenum , New York , 85--103. R. M. Karp. {n.d.}. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher (Eds.). Plenum, New York, 85--103."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.5555\/1416608.1416612"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21797"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00047-8"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.11.005"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(93)90308-I"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367064.1367068"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230250205"},{"key":"e_1_2_1_64_1","first-page":"1","article-title":"Disconnected cuts in claw-free graphs. In Proceedings of the ESA, LIPIcs 112. Schloss Dagstuhl, Daghstuhl","volume":"61","author":"Martin B.","year":"2018","unstructured":"B. Martin , D. Paulusma , and E. J. van Leeuwen . 2018 . Disconnected cuts in claw-free graphs. In Proceedings of the ESA, LIPIcs 112. Schloss Dagstuhl, Daghstuhl , Germany , 61 : 1 -- 61 :14. B. Martin, D. Paulusma, and E. J. van Leeuwen. 2018. Disconnected cuts in claw-free graphs. In Proceedings of the ESA, LIPIcs 112. Schloss Dagstuhl, Daghstuhl, Germany, 61:1--61:14.","journal-title":"Germany"},{"key":"e_1_2_1_65_1","unstructured":"B. Martin D. Paulusma and E. J. van Leeuwen. 2018. Disconnected cuts in claw-free graphs. arXiv:1803.03663. B. Martin D. Paulusma and E. J. van Leeuwen. 2018. Disconnected cuts in claw-free graphs. arXiv:1803.03663."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/11847250_14"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90074-X"},{"key":"e_1_2_1_68_1","volume-title":"Proceedings of the FSTTCS, K. Lodaya and M. Mahajan (Eds.), LIPIcs 8. Schloss Dagstuhl","author":"Misra N.","unstructured":"N. Misra , G. Philip , V. Raman , and S. Saurabh . 2010. The effect of girth on the kernelization complexity of connected dominating set . In Proceedings of the FSTTCS, K. Lodaya and M. Mahajan (Eds.), LIPIcs 8. Schloss Dagstuhl , Daghstuhl, Germany, 96--107. N. Misra, G. Philip, V. Raman, and S. Saurabh. 2010. The effect of girth on the kernelization complexity of connected dominating set. In Proceedings of the FSTTCS, K. Lodaya and M. Mahajan (Eds.), LIPIcs 8. Schloss Dagstuhl, Daghstuhl, Germany, 96--107."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.06.012"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.15807\/jorsj.44.194"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9630-x"},{"key":"e_1_2_1_72_1","unstructured":"P. Nobili and A. Sassano. 2015. An O(n2<\/sup> log(n)) algorithm for the weighted stable set problem in claw-free graphs. arXiv:1501.05775. P. Nobili and A. Sassano. 2015. An O ( n 2<\/sup> log( n )) algorithm for the weighted stable set problem in claw-free graphs. arXiv:1501.05775."},{"key":"e_1_2_1_73_1","volume-title":"Proceedings of the IPCO, A. Lodi, A. Panconesi, and G. Rinaldi (Eds.), LNCS 5035","author":"Oriolo G.","unstructured":"G. Oriolo , U. Pietropaoli , and G. Stauffer . 2008. A new algorithm for the maximum weighted stable set problem in claw-free graphs . In Proceedings of the IPCO, A. Lodi, A. Panconesi, and G. Rinaldi (Eds.), LNCS 5035 . Springer-Verlag, Berlin, 77--96. G. Oriolo, U. Pietropaoli, and G. Stauffer. 2008. A new algorithm for the maximum weighted stable set problem in claw-free graphs. In Proceedings of the IPCO, A. Lodi, A. Panconesi, and G. Rinaldi (Eds.), LNCS 5035. Springer-Verlag, Berlin, 77--96."},{"key":"e_1_2_1_74_1","volume-title":"Proceedings of the ESA, A. Fiat and P. Sanders (Eds.), LNCS 5757","author":"Philip G.","unstructured":"G. Philip , V. Raman , and S. Sikdar . 2009. Solving dominating set in larger classes of graphs: FPT algorithms and polynomial kernels . In Proceedings of the ESA, A. Fiat and P. Sanders (Eds.), LNCS 5757 . Springer-Verlag, Berlin, 694--705. G. Philip, V. Raman, and S. Sikdar. 2009. Solving dominating set in larger classes of graphs: FPT algorithms and polynomial kernels. In Proceedings of the ESA, A. Fiat and P. Sanders (Eds.), LNCS 5757. Springer-Verlag, Berlin, 694--705."},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00052-9"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(73)90029-X"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90287-R"},{"key":"e_1_2_1_78_1","unstructured":"G. Stauffer. {n.d.}. Personal Communication. G. Stauffer. {n.d.}. Personal Communication."},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.06.022"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1137\/0138030"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3301445","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T12:54:41Z","timestamp":1672577681000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3301445"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,22]]},"references-count":81,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4,30]]}},"alternative-id":["10.1145\/3301445"],"URL":"https:\/\/doi.org\/10.1145\/3301445","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,22]]},"assertion":[{"value":"2017-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}