{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T09:13:59Z","timestamp":1778663639165,"version":"3.51.4"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,7,12]],"date-time":"2020-07-12T00:00:00Z","timestamp":1594512000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100011199","name":"FP7 Ideas: European Research Council","doi-asserted-by":"publisher","award":["306992"],"award-info":[{"award-number":["306992"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"crossref","award":["819416 and 715744"],"award-info":[{"award-number":["819416 and 715744"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"crossref"}]},{"name":"PBC Fellowship Program for Outstanding Post-Doctoral Researchers from China and India"},{"name":"Swarnajayanti Fellowship","award":["DST\/SJF\/MSA01\/2017-18"],"award-info":[{"award-number":["DST\/SJF\/MSA01\/2017-18"]}]},{"DOI":"10.13039\/501100001742","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1176\/18"],"award-info":[{"award-number":["1176\/18"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2018302"],"award-info":[{"award-number":["2018302"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,10,31]]},"abstract":"<jats:p>\n            For a family of graphs \u2131, the W&lt;scp;&gt;eighted&lt;\/scp;&gt; \u2131 V&lt;scp;&gt;ertex&lt;\/scp;&gt; D&lt;scp;&gt;eletion&lt;\/scp;&gt; problem, is defined as follows: given an\n            <jats:italic>n<\/jats:italic>\n            -vertex undirected graph\n            <jats:italic>G<\/jats:italic>\n            and a weight function\n            <jats:italic>w<\/jats:italic>\n            :\n            <jats:italic>V<\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            )\u0890 \u211d, find a minimum weight subset\n            <jats:italic>S<\/jats:italic>\n            \u2286\n            <jats:italic>V<\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            ) such that\n            <jats:italic>G<\/jats:italic>\n            -\n            <jats:italic>S<\/jats:italic>\n            belongs to \u2131. We devise a recursive scheme to obtain O(log\n            <jats:sup>O(1)<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            )-approximation algorithms for such problems, building upon the classical technique of finding\n            <jats:italic>balanced separators<\/jats:italic>\n            . We obtain the first O(log\n            <jats:sup>O(1)<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            )-approximation algorithms for the following problems.\n          <\/jats:p>\n          <jats:p>\n            \u2022 Let\n            <jats:italic>F<\/jats:italic>\n            be a finite set of graphs containing a planar graph, and \u2131=\n            <jats:italic>G<\/jats:italic>\n            (\n            <jats:italic>F<\/jats:italic>\n            ) be the maximal family of graphs such that every graph\n            <jats:italic>H<\/jats:italic>\n            \u2208\n            <jats:italic>G<\/jats:italic>\n            (\n            <jats:italic>F<\/jats:italic>\n            ) excludes all graphs in\n            <jats:italic>F<\/jats:italic>\n            as minors. The vertex deletion problem corresponding to \u2131=\n            <jats:italic>G<\/jats:italic>\n            (\n            <jats:italic>F<\/jats:italic>\n            ) is the W\n            <jats:sc>eighted<\/jats:sc>\n            P\n            <jats:sc>lanar<\/jats:sc>\n            <jats:italic>F<\/jats:italic>\n            -M\n            <jats:sc>inor<\/jats:sc>\n            -F\n            <jats:sc>ree<\/jats:sc>\n            D\n            <jats:sc>eletion<\/jats:sc>\n            (WP\n            <jats:italic>F<\/jats:italic>\n            -MFD) problem. We give a randomized and a deterministic approximation algorithms for WP\n            <jats:italic>F<\/jats:italic>\n            -MFD with ratios O(log\n            <jats:sup>1.5<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) and O(log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ), respectively. Prior to our work, a randomized constant factor approximation algorithm for the\n            <jats:italic>unweighted<\/jats:italic>\n            version was known\u00a0[FOCS 2012]. After our work, a deterministic constant factor approximation algorithm for the\n            <jats:italic>unweighted<\/jats:italic>\n            version was also obtained\u00a0[SODA 2019].\n          <\/jats:p>\n          <jats:p>\n            \u2022 We give an O(log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            )-factor approximation algorithm for W\n            <jats:sc>eighted<\/jats:sc>\n            C\n            <jats:sc>hordal<\/jats:sc>\n            V\n            <jats:sc>ertex<\/jats:sc>\n            D\n            <jats:sc>eletion<\/jats:sc>\n            , the vertex deletion problem to the family of chordal graphs. On the way to this algorithm, we also obtain a constant factor approximation algorithm for M\n            <jats:sc>ulticut<\/jats:sc>\n            on chordal graphs.\n          <\/jats:p>\n          <jats:p>\n            \u2022 We give an O(log\n            <jats:sup>3<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            )-factor approximation algorithm for W\n            <jats:sup>eighted<\/jats:sup>\n            D\n            <jats:sc>istance<\/jats:sc>\n            H\n            <jats:sc>ereditary<\/jats:sc>\n            V\n            <jats:sc>ertex<\/jats:sc>\n            D\n            <jats:sc>eletion<\/jats:sc>\n            .\n          <\/jats:p>\n          <jats:p>\n            We believe that our recursive scheme can be applied to obtain O(log\n            <jats:sup>O(1)<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            )-approximation algorithms for many other problems as well.\n          <\/jats:p>","DOI":"10.1145\/3389338","type":"journal-article","created":{"date-parts":[[2020,7,7]],"date-time":"2020-07-07T12:39:25Z","timestamp":1594125565000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Polylogarithmic Approximation Algorithms for Weighted-\u2131-deletion Problems"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0656-7572","authenticated-orcid":false,"given":"Akanksha","family":"Agrawal","sequence":"first","affiliation":[{"name":"Ben-Gurion University of the Negev, Beersheba, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"University of California Santa Barbara, California, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pranabendu","family":"Misra","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"University of Bergen, Norway and The Institute of Mathematical Sciences, Tharamani, Chennai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Beersheba, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,7,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.90"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480196305124"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.128"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90020-1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796305109"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758777"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0210-9"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910009"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00184-5"},{"key":"e_1_2_1_10_1","volume-title":"Graph Theory","author":"Diestel Reinhard","unstructured":"Reinhard Diestel . 2012. Graph Theory , 4 th ed. Graduate texts in mathematics, Vol. 173 . Springer , Berlin. Reinhard Diestel. 2012. Graph Theory, 4th ed. Graduate texts in mathematics, Vol. 173. Springer, Berlin.","edition":"4"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90268-9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/05064299X"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13036-6_15"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/140997889"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.62"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.59"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.124"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910)","author":"Fomin Fedor V.","year":"1973","unstructured":"Fedor V. Fomin , Daniel Lokshtanov , Saket Saurabh , and Dimitrios M. Thilikos . 2010. Bidimensionality and kernels . In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910) . SIAM, 503--510. DOI:https:\/\/doi.org\/10.1137\/1.978161 1973 075.43 10.1137\/1.9781611973075.43 Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. 2010. Bidimensionality and kernels. In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910). SIAM, 503--510. DOI:https:\/\/doi.org\/10.1137\/1.9781611973075.43"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793243016"},{"key":"e_1_2_1_20_1","volume-title":"Understanding and Using Linear Programming","author":"G\u00e4rtner Bernd","unstructured":"Bernd G\u00e4rtner and Jivr\u2019i Matouvsek . 2007. Understanding and Using Linear Programming . Springer , Berlin . Bernd G\u00e4rtner and Jivr\u2019i Matouvsek. 2007. Understanding and Using Linear Programming. Springer, Berlin."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109625"},{"key":"e_1_2_1_22_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 . Martin Charles Golumbic. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.104"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(90)90131-U"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm052"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/28.4.417"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917)","author":"Bart M.","year":"1974","unstructured":"Bart M. P. Jansen and Marcin Pilipczuk. 2017. Approximation and kernelization for chordal vertex deletion . In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917) . SIAM, 1399--1418. DOI:https:\/\/doi.org\/10.1137\/1.978161 1974 782.91 10.1137\/1.9781611974782.91 Bart M. P. Jansen and Marcin Pilipczuk. 2017. Approximation and kernelization for chordal vertex deletion. In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917). SIAM, 1399--1418. DOI:https:\/\/doi.org\/10.1137\/1.9781611974782.91"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M112035X"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(80)90061-0"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.109"},{"key":"e_1_2_1_32_1","volume-title":"Algorithms and Data Structures","author":"Kim Eun Jung","unstructured":"Eun Jung Kim and O- Joung Kwon . 2017. A polynomial kernel for distance-hereditary vertex deletion . In Algorithms and Data Structures . Springer , Cham , 509--520. DOI:https:\/\/doi.org\/10.1007\/978-3-319-62127-2_43 10.1007\/978-3-319-62127-2_43 Eun Jung Kim and O-Joung Kwon. 2017. A polynomial kernel for distance-hereditary vertex deletion. In Algorithms and Data Structures. Springer, Cham, 509--520. DOI:https:\/\/doi.org\/10.1007\/978-3-319-62127-2_43"},{"key":"e_1_2_1_33_1","unstructured":"Jon M. Kleinberg and \u00c9va Tardos. 2005. Algorithm\u00a0Design. Addison-Wesley Boston.  Jon M. Kleinberg and \u00c9va Tardos. 2005. Algorithm\u00a0Design. Addison-Wesley Boston."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-56939-1_60"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760024"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580222"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.03.003"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"ACM Trans. Algor. 2008 5 Approximating rank-width and clique-width quickly","DOI":"10.1145\/1435375.1435385"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2016.08.006"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.10.006"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"e_1_2_1_46_1","first-page":"384","article-title":"On the Berge conjecture concerning perfect graphs","volume":"37","author":"Sachs Horst","year":"1970","unstructured":"Horst Sachs . 1970 . On the Berge conjecture concerning perfect graphs . Combin. Struct. Their Appl. 37 (1970), 384 . Horst Sachs. 1970. On the Berge conjecture concerning perfect graphs. Combin. Struct. Their Appl. 37 (1970), 384.","journal-title":"Combin. Struct. Their Appl."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)90092-2"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206036"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322157"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57811-0_4"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3389338","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3389338","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:31Z","timestamp":1750200091000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3389338"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,12]]},"references-count":50,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,10,31]]}},"alternative-id":["10.1145\/3389338"],"URL":"https:\/\/doi.org\/10.1145\/3389338","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,12]]},"assertion":[{"value":"2019-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}