{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T21:14:29Z","timestamp":1768511669326,"version":"3.49.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T00:00:00Z","timestamp":1591401600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Parameterized Approximation","award":["306992"],"award-info":[{"award-number":["306992"]}]},{"name":"Pareto-Optimal Parameterized Algorithms","award":["715744"],"award-info":[{"award-number":["715744"]}]},{"DOI":"10.13039\/501100005416","name":"Norwegian Research Council","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Swarnajayanti Fellowship","award":["DST\/SJF\/MSA-01\/2017-18"],"award-info":[{"award-number":["DST\/SJF\/MSA-01\/2017-18"]}]},{"name":"European Research Council","award":["819416"],"award-info":[{"award-number":["819416"]}]},{"name":"Rigorous Theory of Preprocessing","award":["267959"],"award-info":[{"award-number":["267959"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,7,31]]},"abstract":"<jats:p>\n            We present two new combinatorial tools for the design of parameterized algorithms. The first is a simple linear time randomized algorithm that given as input a\n            <jats:italic>d<\/jats:italic>\n            -degenerate graph\n            <jats:italic>G<\/jats:italic>\n            and an integer\n            <jats:italic>k<\/jats:italic>\n            , outputs an independent set\n            <jats:italic>Y<\/jats:italic>\n            , such that for every independent set\n            <jats:italic>X<\/jats:italic>\n            in\n            <jats:italic>G<\/jats:italic>\n            of size at most\n            <jats:italic>k<\/jats:italic>\n            , the probability that\n            <jats:italic>X<\/jats:italic>\n            is a subset of\n            <jats:italic>Y<\/jats:italic>\n            is at least ((\n            <jats:sup>(d+1)k<\/jats:sup>\n            <jats:sub>k<\/jats:sub>\n            ) .\n            <jats:italic>k<\/jats:italic>\n            (d+1))\n            <jats:sup>-1<\/jats:sup>\n            . The second is a new (deterministic) polynomial time graph sparsification procedure that given a graph\n            <jats:italic>G<\/jats:italic>\n            , a set\n            <jats:italic>T<\/jats:italic>\n            = {s_1, t_1} , {s_2, t_2}, \u2026. , {s_\u2113 , t_\u2113} of terminal pairs, and an integer\n            <jats:italic>k<\/jats:italic>\n            , returns an induced subgraph\n            <jats:italic>G*<\/jats:italic>\n            of\n            <jats:italic>G<\/jats:italic>\n            that maintains\n            <jats:italic>all<\/jats:italic>\n            the inclusion minimal multicuts of\n            <jats:italic>G<\/jats:italic>\n            of size at most\n            <jats:italic>k<\/jats:italic>\n            and does not contain any (\n            <jats:italic>k<\/jats:italic>\n            +2)-vertex connected set of size 2\n            <jats:sup>O(k)<\/jats:sup>\n            . In particular,\n            <jats:italic>G*<\/jats:italic>\n            excludes a clique of size 2\n            <jats:sup>O(k)<\/jats:sup>\n            as a topological minor. Put together, our new tools yield new randomized fixed parameter tractable (FPT) algorithms for S\n            <jats:sc>TABLE<\/jats:sc>\n            <jats:italic>s-t<\/jats:italic>\n            S\n            <jats:sc>EPARATOR<\/jats:sc>\n            , S\n            <jats:sc>TABLE<\/jats:sc>\n            O\n            <jats:sc>DD<\/jats:sc>\n            C\n            <jats:sc>YCLE<\/jats:sc>\n            T\n            <jats:sc>RANSVERSAL<\/jats:sc>\n            , and S\n            <jats:sc>TABLE<\/jats:sc>\n            M\n            <jats:sc>ULTICUT<\/jats:sc>\n            on general graphs, and for S\n            <jats:sc>TABLE<\/jats:sc>\n            D\n            <jats:sc>IRECTED<\/jats:sc>\n            F\n            <jats:sc>EEDBACK<\/jats:sc>\n            V\n            <jats:sc>ERTEX<\/jats:sc>\n            S\n            <jats:sc>ET<\/jats:sc>\n            on\n            <jats:italic>d<\/jats:italic>\n            -degenerate graphs, resolving two problems left open by Marx et\u00a0al. [\n            <jats:italic>ACM Transactions on Algorithms,<\/jats:italic>\n            2013{. All of our algorithms can be derandomized at the cost of a small overhead in the running time.\n          <\/jats:p>","DOI":"10.1145\/3379698","type":"journal-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T00:47:00Z","timestamp":1591490820000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms"],"prefix":"10.1145","volume":"16","author":[{"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[{"name":"University of California, Santa Barbara, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, IIT Hyderabad, Sangareddy, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"Institute of Mathematical Sciences, HBNI, India, University of Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roohani","family":"Sharma","sequence":"additional","affiliation":[{"name":"Institute of Mathematical Sciences, HBNI, Chennai, Tamil Nadu, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[{"name":"Ben-Gurion University, Beersheva, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/307654.307655"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993698"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/302970"},{"key":"e_1_2_1_4_1","volume-title":"Bshouty and Ariel Gabizon","author":"Nader","year":"2017","unstructured":"Nader H. Bshouty and Ariel Gabizon . 2017 . Almost optimal cover-free families. In Proceedings of the International Conference on Algorithms and Complexity. Springer , 140--151. Nader H. Bshouty and Ariel Gabizon. 2017. Almost optimal cover-free families. In Proceedings of the International Conference on Algorithms and Complexity. Springer, 140--151."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9130-6"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411511"},{"key":"e_1_2_1_7_1","first-page":"28","article-title":"Directed subset feedback vertex set is fixed-parameter tractable","volume":"11","author":"Chitnis Rajesh Hemant","year":"2015","unstructured":"Rajesh Hemant Chitnis , Marek Cygan , Mohammad Taghi Hajiaghayi , and D\u00e1niel Marx . 2015 . Directed subset feedback vertex set is fixed-parameter tractable . ACM Trans. Algor. 11 , 4 (2015), 28 . Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, and D\u00e1niel Marx. 2015. Directed subset feedback vertex set is fixed-parameter tractable. ACM Trans. Algor. 11, 4 (2015), 28.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/12086217X"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0402004"},{"key":"e_1_2_1_10_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2009. Introduction to Algorithms . The MIT Press . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms. The MIT Press."},{"key":"e_1_2_1_11_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek","unstructured":"Marek Cygan , Fedor V. Fomin , \u0141ukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Micha\u0142 Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . Marek Cygan, Fedor V. Fomin, \u0141ukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Micha\u0142 Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"e_1_2_1_12_1","unstructured":"Marek Cygan \u0141ukasz Kowalik and Marcin Pilipczuk. 2013a. Open problems from the update meeting on graph separation problems. http:\/\/worker2013.mimuw.edu.pl\/slides\/update-opl.pdf.  Marek Cygan \u0141ukasz Kowalik and Marcin Pilipczuk. 2013a. Open problems from the update meeting on graph separation problems. http:\/\/worker2013.mimuw.edu.pl\/slides\/update-opl.pdf."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/110843071"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792225297"},{"key":"e_1_2_1_15_1","first-page":"07","article-title":"07281 open problems\u2014Structure theory and FPT algorithmcs for graphs, digraphs and hypergraphs","volume":"08","author":"Demaine Erik D.","year":"2007","unstructured":"Erik D. Demaine , Gregory Gutin , D\u00e1niel Marx , and Ulrike Stege . 2007 . 07281 open problems\u2014Structure theory and FPT algorithmcs for graphs, digraphs and hypergraphs . In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs , 08 . 07 .2007\u201313.07.2007. Erik D. Demaine, Gregory Gutin, D\u00e1niel Marx, and Ulrike Stege. 2007. 07281 open problems\u2014Structure theory and FPT algorithmcs for graphs, digraphs and hypergraphs. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs, 08.07.2007\u201313.07.2007.","journal-title":"Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs"},{"key":"e_1_2_1_16_1","volume-title":"Graph Theory","author":"Diestel R.","unstructured":"R. Diestel . 2000. Graph Theory ( 2 nd ed.). Springer , Berlin . R. Diestel. 2000. Graph Theory (2nd ed.). Springer, Berlin.","edition":"2"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201913)","volume":"24","author":"Grohe Martin","year":"2013","unstructured":"Martin Grohe , Stephan Kreutzer , and Sebastian Siebertz . 2013 . Characterisations of nowhere dense graphs (invited talk) . In Proceedings of the Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201913) (LIPIcs), Vol. 24 . 21--40. Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. 2013. Characterisations of nowhere dense graphs (invited talk). In Proceedings of the Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201913) (LIPIcs), Vol. 24. 21--40."},{"key":"e_1_2_1_19_1","volume-title":"Orlin","author":"Hao Jianxiu","year":"1992","unstructured":"Jianxiu Hao and James B . Orlin . 1992 . A faster algorithm for finding the minimum cut in a graph. In Proceedings of the 3rd ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 165--174. Jianxiu Hao and James B. Orlin. 1992. A faster algorithm for finding the minimum cut in a graph. In Proceedings of the 3rd ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 165--174."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.127"},{"key":"e_1_2_1_21_1","volume-title":"Complexity of Computer Computations","author":"Karp Richard M.","unstructured":"Richard M. Karp . 1972. Reducibility among combinatorial problems . In Complexity of Computer Computations . Springer , 85--103. Richard M. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations. Springer, 85--103."},{"key":"e_1_2_1_22_1","volume-title":"Reed","author":"Kawarabayashi","year":"2010","unstructured":"Ken-ichi Kawarabayashi and Bruce A . Reed . 2010 . An (almost) linear time algorithm for odd cycles transversal. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910). 365--378. Ken-ichi Kawarabayashi and Bruce A. Reed. 2010. An (almost) linear time algorithm for odd cycles transversal. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910). 365--378."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830000184X"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/120904202"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.46"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.016"},{"key":"e_1_2_1_27_1","article-title":"Faster parameterized algorithms using linear programming","volume":"11","author":"Lokshtanov Daniel","year":"2014","unstructured":"Daniel Lokshtanov , N. S. Narayanaswamy , Venkatesh Raman , M. S. Ramanujan , and Saket Saurabh . 2014 . Faster parameterized algorithms using linear programming . ACM Trans. Algor. 11 , 2 (2014), 15:1\u201315:31. Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. 2014. Faster parameterized algorithms using linear programming. ACM Trans. Algor. 11, 2 (2014), 15:1\u201315:31.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP\u201912)","author":"Lokshtanov Daniel","unstructured":"Daniel Lokshtanov and M. S. Ramanujan . 2012. Parameterized tractability of multiway cut with parity constraints . In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP\u201912) . 750--761. Daniel Lokshtanov and M. S. Ramanujan. 2012. Parameterized tractability of multiway cut with parity constraints. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP\u201912). 750--761."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_76"},{"key":"e_1_2_1_30_1","volume-title":"A linear time parameterized algorithm for directed feedback vertex set. CoRR abs\/1609.04347","author":"Lokshtanov Daniel","year":"2016","unstructured":"Daniel Lokshtanov , M. S. Ramanujan , and Saket Saurabh . 2016a. A linear time parameterized algorithm for directed feedback vertex set. CoRR abs\/1609.04347 ( 2016 ). Daniel Lokshtanov, M. S. Ramanujan, and Saket Saurabh. 2016a. A linear time parameterized algorithm for directed feedback vertex set. CoRR abs\/1609.04347 (2016)."},{"key":"e_1_2_1_31_1","volume-title":"A linear time parameterized algorithm for node unique label cover. CoRR abs\/1604.08764","author":"Lokshtanov Daniel","year":"2016","unstructured":"Daniel Lokshtanov , M. S. Ramanujan , and Saket Saurabh . 2016b. A linear time parameterized algorithm for node unique label cover. CoRR abs\/1604.08764 ( 2016 ). Daniel Lokshtanov, M. S. Ramanujan, and Saket Saurabh. 2016b. A linear time parameterized algorithm for node unique label cover. CoRR abs\/1604.08764 (2016)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02993903"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.007"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25870-1_2"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500119"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/110855247"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.02.012"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.07.013"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the European Congress of Mathematics. 135--165","author":"Ne\u0161etril Jaroslav","year":"2009","unstructured":"Jaroslav Ne\u0161etril and Patrice Ossona de Mendez . 2009 . From sparse graphs to nowhere dense structures: Decompositions, independence, dualities. and limits . In Proceedings of the European Congress of Mathematics. 135--165 . Jaroslav Ne\u0161etril and Patrice Ossona de Mendez. 2009. From sparse graphs to nowhere dense structures: Decompositions, independence, dualities. and limits. In Proceedings of the European Congress of Mathematics. 135--165."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.01.006"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Jaroslav Ne\u0161et\u0159il and Patrice Ossona de Mendez. 2012. Sparsity\u2014Graphs Structures and Algorithms. (Algorithms and Combinatorics Vol. 28).Springer.  Jaroslav Ne\u0161et\u0159il and Patrice Ossona de Mendez. 2012. Sparsity\u2014Graphs Structures and Algorithms. (Algorithms and Combinatorics Vol. 28).Springer.","DOI":"10.1007\/978-3-642-27875-4"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3201775"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.126"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263872"},{"key":"e_1_2_1_48_1","volume-title":"Graph theory. Lect. Notes","author":"Sudakov Benny","year":"2016","unstructured":"Benny Sudakov . 2016. Graph theory. Lect. Notes ( 2016 ). http:\/\/www2.math.ethz.ch\/education\/bachelor\/lectures\/fs2016\/math\/graph_theory\/graph_theory_notes.pdf. Benny Sudakov. 2016. Graph theory. Lect. Notes (2016). http:\/\/www2.math.ethz.ch\/education\/bachelor\/lectures\/fs2016\/math\/graph_theory\/graph_theory_notes.pdf."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3379698","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3379698","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:20Z","timestamp":1750200080000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3379698"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,6]]},"references-count":48,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,7,31]]}},"alternative-id":["10.1145\/3379698"],"URL":"https:\/\/doi.org\/10.1145\/3379698","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,6]]},"assertion":[{"value":"2018-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}