{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:16:20Z","timestamp":1761621380531,"version":"3.41.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,5,6]],"date-time":"2018-05-06T00:00:00Z","timestamp":1525564800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Warsaw Center of Mathematics and Computer Science"},{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["UMO-2013\/11\/D\/ST6\/03073"],"award-info":[{"award-number":["UMO-2013\/11\/D\/ST6\/03073"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme","award":["677651"],"award-info":[{"award-number":["677651"]}]},{"name":"Government of the Russian Federation","award":["14.Z50.31.0030"],"award-info":[{"award-number":["14.Z50.31.0030"]}]},{"name":"Grant of the President of the Russian Federation","award":["MK-6550.2015.1"],"award-info":[{"award-number":["MK-6550.2015.1"]}]},{"name":"Foundation for Polish Science (FNP) via the START stipend programme"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2018,6,30]]},"abstract":"<jats:p>\n            The\n            <jats:italic>H<\/jats:italic>\n            -\n            <jats:sc>free<\/jats:sc>\n            E\n            <jats:sc>dge<\/jats:sc>\n            D\n            <jats:sc>eletion<\/jats:sc>\n            problem asks, for a given graph\n            <jats:italic>G<\/jats:italic>\n            and integer\n            <jats:italic>k<\/jats:italic>\n            , whether it is possible to delete at most\n            <jats:italic>k<\/jats:italic>\n            edges from\n            <jats:italic>G<\/jats:italic>\n            to make it\n            <jats:italic>H<\/jats:italic>\n            -free\u2014that is, not containing\n            <jats:italic>H<\/jats:italic>\n            as an induced subgraph. The\n            <jats:italic>H<\/jats:italic>\n            -\n            <jats:sc>free<\/jats:sc>\n            E\n            <jats:sc>dge<\/jats:sc>\n            C\n            <jats:sc>ompletion<\/jats:sc>\n            problem is defined similarly, but we add edges instead of deleting them. The study of these two problem families has recently been the subject of intensive studies from the point of view of parameterized complexity and kernelization. In particular, it was shown that the problems do not admit polynomial kernels (under plausible complexity assumptions) for almost all graphs\n            <jats:italic>H<\/jats:italic>\n            , with several important exceptions occurring when the class of\n            <jats:italic>H<\/jats:italic>\n            -free graphs exhibits some structural properties.\n          <\/jats:p>\n          <jats:p>\n            In this work, we complement the parameterized study of edge modification problems to\n            <jats:italic>H<\/jats:italic>\n            -free graphs by considering their approximability. We prove that whenever\n            <jats:italic>H<\/jats:italic>\n            is 3-connected and has at least two nonedges, then both\n            <jats:italic>H<\/jats:italic>\n            -\n            <jats:sc>free<\/jats:sc>\n            E\n            <jats:sc>dge<\/jats:sc>\n            D\n            <jats:sc>eletion<\/jats:sc>\n            and\n            <jats:italic>H<\/jats:italic>\n            -\n            <jats:sc>free<\/jats:sc>\n            E\n            <jats:sc>dge<\/jats:sc>\n            C\n            <jats:sc>ompletion<\/jats:sc>\n            are very hard to approximate: they do not admit poly(OPT)-approximation in polynomial time, unless P=NP, or even in time subexponential in OPT, unless the exponential time hypothesis fails. The assumption of the existence of two nonedges appears to be important: we show that whenever\n            <jats:italic>H<\/jats:italic>\n            is a complete graph without one edge, then\n            <jats:italic>H<\/jats:italic>\n            -\n            <jats:sc>free<\/jats:sc>\n            E\n            <jats:sc>dge<\/jats:sc>\n            D\n            <jats:sc>eletion<\/jats:sc>\n            is tightly connected to the M\n            <jats:sc>in<\/jats:sc>\n            H\n            <jats:sc>orn<\/jats:sc>\n            D\n            <jats:sc>eletion<\/jats:sc>\n            problem, whose approximability is still open. Finally, in an attempt to extend our hardness results beyond 3-connected graphs, we consider the cases of\n            <jats:italic>H<\/jats:italic>\n            being a path or a cycle, and we achieve an almost complete dichotomy there.\n          <\/jats:p>","DOI":"10.1145\/3196834","type":"journal-article","created":{"date-parts":[[2018,5,7]],"date-time":"2018-05-07T12:05:27Z","timestamp":1525694727000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Hardness of Approximation for\n            <i>H<\/i>\n            -free Edge Modification Problems"],"prefix":"10.1145","volume":"10","author":[{"given":"Ivan","family":"Bliznets","sequence":"first","affiliation":[{"name":"St.\u00a0Petersburg Department of Steklov Institute of Mathematics, St. Petersburg, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Cygan","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"Komosa","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,5,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1055797"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884514"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00050-6"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9937-x"},{"volume-title":"Polynomial Kernelisation of H-free edge Modification Problems. Master\u2019s Thesis","author":"Cai Yufei","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9689-x"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2799640"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1038876"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9619-5"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796303044"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799349948"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2013.02.001"},{"key":"e_1_2_1_14_1","first-page":"41","article-title":"Lower bounds based on the exponential time hypothesis","volume":"105","author":"Lokshtanov Daniel","year":"2011","journal-title":"Bulletin of the EATCS"},{"volume-title":"Complexity and Approximation of Some Graph Modification Problems. Master\u2019s Thesis. Department of Computer Science","author":"Natanzon Assaf","key":"e_1_2_1_15_1"},{"volume":"43","volume-title":"10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs)","author":"Sandeep R. B.","key":"e_1_2_1_16_1"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3196834","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3196834","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:29Z","timestamp":1750210769000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3196834"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,6]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,6,30]]}},"alternative-id":["10.1145\/3196834"],"URL":"https:\/\/doi.org\/10.1145\/3196834","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2018,5,6]]},"assertion":[{"value":"2016-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-05-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}