{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T13:42:07Z","timestamp":1772372527904,"version":"3.50.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,8,31]],"date-time":"2015-08-31T00:00:00Z","timestamp":1440979200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC","award":["267959"],"award-info":[{"award-number":["267959"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2015,9,11]]},"abstract":"\n Let\n F<\/jats:italic>\n be a family of graphs. In the\n F<\/jats:italic>\n -C\n ompletion<\/jats:sc>\n problem, we are given an\n n<\/jats:italic>\n -vertex graph\n G<\/jats:italic>\n and an integer\n k<\/jats:italic>\n as input, and asked whether at most\n k<\/jats:italic>\n edges can be added to\n G<\/jats:italic>\n so that the resulting graph does not contain a graph from\n F<\/jats:italic>\n as an induced subgraph. It was shown recently that two special cases of\n F<\/jats:italic>\n -C\n ompletion<\/jats:sc>\n , namely, (i) the problem of completing into a chordal graph known as M\n inimum<\/jats:sc>\n F\n ill-in<\/jats:sc>\n (SIAM J. Comput. 2013), which corresponds to the case of\n F<\/jats:italic>\n ={\n C<\/jats:italic>\n 4<\/jats:sub>\n ,\n C<\/jats:italic>\n 5<\/jats:sub>\n ,\n C<\/jats:italic>\n 6<\/jats:sub>\n , \u2026}, and (ii) the problem of completing into a split graph (Algorithmica 2015), that is, the case of\n F<\/jats:italic>\n ={\n C<\/jats:italic>\n 4<\/jats:sub>\n , 2\n K<\/jats:italic>\n 2<\/jats:sub>\n ,\n C<\/jats:italic>\n 5<\/jats:sub>\n }, are solvable in parameterized subexponential time 2\n \n O<\/jats:italic>\n (\u221a\n k<\/jats:italic>\n log\n k<\/jats:italic>\n )\n <\/jats:sup>\n n<\/jats:italic>\n \n O<\/jats:italic>\n (1)\n <\/jats:sup>\n . The exploration of this phenomenon is the main motivation for our research on\n F<\/jats:italic>\n -C\n ompletion<\/jats:sc>\n .\n <\/jats:p>\n In this article, we prove that completions into several well-studied classes of graphs without long induced cycles and paths also admit parameterized subexponential time algorithms by showing that:<\/jats:p>\n \n \u2014The problem T\n rivially<\/jats:sc>\n P\n erfect<\/jats:sc>\n C\n ompletion<\/jats:sc>\n , which is\n F<\/jats:italic>\n -\n C<\/jats:italic>\n ompletion<\/jats:sc>\n for\n F<\/jats:italic>\n ={\n C<\/jats:italic>\n 4<\/jats:sub>\n ,\n P<\/jats:italic>\n 4<\/jats:sub>\n }, a cycle and a path on four vertices, is solvable in parameterized subexponential time 2\n \n O<\/jats:italic>\n (\u221a\n k<\/jats:italic>\n log\n k<\/jats:italic>\n )\n <\/jats:sup>\n n<\/jats:italic>\n \n O<\/jats:italic>\n (1)\n <\/jats:sup>\n .\n <\/jats:p>\n \n \u2014The problems known in the literature as P\n seudosplit<\/jats:sc>\n C\n ompletion<\/jats:sc>\n , the case in which F{2\n K<\/jats:italic>\n 2<\/jats:sub>\n ,\n C<\/jats:italic>\n 4<\/jats:sub>\n }, and T\n hreshold<\/jats:sc>\n C\n ompletion<\/jats:sc>\n , in which\n F<\/jats:italic>\n =2\n K<\/jats:italic>\n 2<\/jats:sub>\n ,\n P<\/jats:italic>\n 4<\/jats:sub>\n ,\n C<\/jats:italic>\n 4<\/jats:sub>\n }, are also solvable in time 2\n \n O<\/jats:italic>\n (\u221a\n k<\/jats:italic>\n log\n k<\/jats:italic>\n )\n <\/jats:sup>\n n<\/jats:italic>\n \n O<\/jats:italic>\n }(1)\n <\/jats:sup>\n .\n <\/jats:p>\n \n We complement our algorithms for\n F<\/jats:italic>\n -C\n ompletion<\/jats:sc>\n with the following lower bounds:\n <\/jats:p>\n \n \u2014For\n F<\/jats:italic>\n ={2\n K<\/jats:italic>\n 2<\/jats:sub>\n },\n F<\/jats:italic>\n = {\n C<\/jats:italic>\n 4<\/jats:sub>\n },\n F<\/jats:italic>\n ={\n P<\/jats:italic>\n o\n 4<\/jats:sub>\n }, and\n F<\/jats:italic>\n ={2\n K<\/jats:italic>\n 2<\/jats:sub>\n ,\n P<\/jats:italic>\n 4<\/jats:sub>\n },\n F<\/jats:italic>\n -C\n ompletion<\/jats:sc>\n cannot be solved in time 2\n \n o(k)<\/jats:italic>\n <\/jats:sup>\n n<\/jats:italic>\n \n O<\/jats:italic>\n (1)\n <\/jats:sup>\n unless the Exponential Time Hypothesis (ETH) fails.\n <\/jats:p>\n \n Our upper and lower bounds provide a complete picture of the subexponential parameterized complexity of\n F<\/jats:italic>\n -C\n ompletion<\/jats:sc>\n problems for any\n F<\/jats:italic>\n \u2286 {2\n K<\/jats:italic>\n 2<\/jats:sub>\n ,\n C<\/jats:italic>\n 4<\/jats:sub>\n ,\n P<\/jats:italic>\n 4<\/jats:sub>\n }.\n <\/jats:p>","DOI":"10.1145\/2799640","type":"journal-article","created":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T13:41:09Z","timestamp":1441114869000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Exploring the Subexponential Complexity of Completion Problems"],"prefix":"10.1145","volume":"7","author":[{"given":"P\u00e5l Gr\u00f8n\u00e5s","family":"Drange","sequence":"first","affiliation":[{"name":"Department of Informatics, University of Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yngve","family":"Villanger","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,8,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_6"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Ivan Bliznets Fedor V. Fomin Marcin Pilipczuk and Micha\u0142 Pilipczuk. 2014a. A subexponential parameterized algorithm for interval completion. CoRR abs\/1402.3473. Ivan Bliznets Fedor V. Fomin Marcin Pilipczuk and Micha\u0142 Pilipczuk. 2014a. A subexponential parameterized algorithm for interval completion. CoRR abs\/1402.3473.","DOI":"10.1007\/978-3-662-44777-2_15"},{"key":"e_1_2_1_3_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the European Symposium on Algorithms (ESA)","author":"Bliznets Ivan","unstructured":"Ivan Bliznets , Fedor V. Fomin , Marcin Pilipczuk , and Micha\u0142 Pilipczuk . 2014b. A subexponential parameterized algorithm for proper interval completion . In Proceedings of the European Symposium on Algorithms (ESA) . Lecture Notes in Computer Science , Vol. 8737 . Springer , Berlin , 173--184. Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, and Micha\u0142 Pilipczuk. 2014b. A subexponential parameterized algorithm for proper interval completion. In Proceedings of the European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, Vol. 8737. Springer, Berlin, 173--184."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"e_1_2_1_5_1","volume-title":"Van Bang Le, and Jeremy P. Spinrad","author":"Brandst\u00e4dt Andreas","year":"1999","unstructured":"Andreas Brandst\u00e4dt , Van Bang Le, and Jeremy P. Spinrad . 1999 . Graph Classes. A Survey. SIAM , Philadelphia, PA. Andreas Brandst\u00e4dt, Van Bang Le, and Jeremy P. Spinrad. 1999. Graph Classes. A Survey. SIAM, Philadelphia, PA."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.03.031"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00050-6"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9937-x"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS) (LIPIcs)","volume":"25","author":"Drange P\u00e5l Gr\u00f8n\u00e5s","year":"2014","unstructured":"P\u00e5l Gr\u00f8n\u00e5s Drange , Fedor V. Fomin , Micha\u0142 Pilipczuk , and Yngve Villanger . 2014 . Exploring subexponential parameterized complexity of completion problems . In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS) (LIPIcs) , Vol. 25 . Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik, 288--299. P\u00e5l Gr\u00f8n\u00e5s Drange, Fedor V. Fomin, Micha\u0142 Pilipczuk, and Yngve Villanger. 2014. Exploring subexponential parameterized complexity of completion problems. In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS) (LIPIcs), Vol. 25. Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik, 288--299."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_36"},{"key":"e_1_2_1_12_1","volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","unstructured":"J\u00f6rg Flum and Martin Grohe . 2006. Parameterized Complexity Theory . Springer-Verlag , New York . J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag, New York."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2014.04.015"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085390X"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9837-5"},{"key":"e_1_2_1_16_1","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic Martin Charles","unstructured":"Martin Charles Golumbic . 1980. Algorithmic Graph Theory and Perfect Graphs . Academic Press , New York, NY . Martin Charles Golumbic. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, NY."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9619-5"},{"key":"e_1_2_1_18_1","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithms and Computation, 18th International Symposium (ISAAC)","author":"Guo Jiong","unstructured":"Jiong Guo . 2007. Problem kernels for NP-complete edge deletion problems: Split and related graphs . In Algorithms and Computation, 18th International Symposium (ISAAC) . Lecture Notes in Computer Science , Vol. 4835 . Springer , Berlin , 915--926. Jiong Guo. 2007. Problem kernels for NP-complete edge deletion problems: Split and related graphs. In Algorithms and Computation, 18th International Symposium (ISAAC). Lecture Notes in Computer Science, Vol. 4835. Springer, Berlin, 915--926."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(96)00094-7"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793258143"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796303044"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.05.019"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2013.02.001"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00022-0"},{"key":"e_1_2_1_26_1","volume-title":"Peled","author":"Mahadev Nadimpalli V. R.","year":"1995","unstructured":"Nadimpalli V. R. Mahadev and Uri N . Peled . 1995 . Threshold Graphs and Related Topics. Annals of Discrete Mathematics, Vol. 56 . Elsevier . Nadimpalli V. R. Mahadev and Uri N. Peled. 1995. Threshold Graphs and Related Topics. Annals of Discrete Mathematics, Vol. 56. Elsevier."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798336073"},{"key":"e_1_2_1_29_1","volume-title":"Algorithms and combinatorics","author":"Ne\u0161et\u0159il Jaroslav","unstructured":"Jaroslav Ne\u0161et\u0159il and Patrice Ossona de Mendez . 2012. Sparsity -- Graphs , Structures, and Algorithms. Algorithms and combinatorics , Vol. 28 . Springer . Jaroslav Ne\u0161et\u0159il and Patrice Ossona de Mendez. 2012. Sparsity -- Graphs, Structures, and Algorithms. Algorithms and combinatorics, Vol. 28. Springer."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/070710913"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0602010"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210021"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2799640","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2799640","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:42:43Z","timestamp":1750225363000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2799640"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8,31]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,9,11]]}},"alternative-id":["10.1145\/2799640"],"URL":"https:\/\/doi.org\/10.1145\/2799640","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,8,31]]},"assertion":[{"value":"2014-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-08-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}