{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T17:25:16Z","timestamp":1784568316978,"version":"3.55.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,10,30]],"date-time":"2014-10-30T00:00:00Z","timestamp":1414627200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/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":[[2014,11,17]]},"abstract":"<jats:p>\n            We investigate the parameterized complexity of\n            <jats:sc>Vertex Cover<\/jats:sc>\n            parameterized by the difference between the size of the optimal solution and the value of the linear programming (LP) relaxation of the problem. By carefully analyzing the change in the LP value in the branching steps, we argue that combining previously known preprocessing rules with the most straightforward branching algorithm yields an\n            <jats:italic>O<\/jats:italic>\n            *(2.618\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            ) algorithm for the problem. Here,\n            <jats:italic>k<\/jats:italic>\n            is the excess of the vertex cover size over the LP optimum, and we write\n            <jats:italic>O<\/jats:italic>\n            *(\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            )) for a time complexity of the form\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            )\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            ). We proceed to show that a more sophisticated branching algorithm achieves a running time of\n            <jats:italic>O<\/jats:italic>\n            *(2.3146\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            ).\n          <\/jats:p>\n          <jats:p>\n            Following this, using previously known as well as new reductions, we give\n            <jats:italic>O<\/jats:italic>\n            *(2.3146\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            ) algorithms for the parameterized versions of\n            <jats:sc>Above Guarantee Vertex Cover<\/jats:sc>\n            ,\n            <jats:sc>Odd Cycle Transversal<\/jats:sc>\n            ,\n            <jats:sc>Split Vertex Deletion,<\/jats:sc>\n            and\n            <jats:sc>Almost 2-SAT<\/jats:sc>\n            , and\n            <jats:italic>O<\/jats:italic>\n            *(1.5214\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            ) algorithms for\n            <jats:sc>K\u00f6nig Vertex Deletion<\/jats:sc>\n            and\n            <jats:sc>Vertex Cover<\/jats:sc>\n            parameterized by the size of the smallest odd cycle transversal and K\u00f6nig vertex deletion set. These algorithms significantly improve the best known bounds for these problems. The most notable improvement among these is the new bound for\n            <jats:sc>Odd Cycle Transversal<\/jats:sc>\n            \u2014this is the first algorithm that improves on the dependence on\n            <jats:italic>k<\/jats:italic>\n            of the seminal\n            <jats:italic>O<\/jats:italic>\n            *(3\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            ) algorithm of Reed, Smith, and Vetta. Finally, using our algorithm, we obtain a kernel for the standard parameterization of\n            <jats:sc>Vertex Cover<\/jats:sc>\n            with at most 2\n            <jats:italic>k<\/jats:italic>\n            \u2212\n            <jats:italic>c<\/jats:italic>\n            log\n            <jats:italic>k<\/jats:italic>\n            vertices. Our kernel is simpler than previously known kernels achieving the same size bound.\n          <\/jats:p>","DOI":"10.1145\/2566616","type":"journal-article","created":{"date-parts":[[2014,10,31]],"date-time":"2014-10-31T19:28:54Z","timestamp":1414783734000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":93,"title":["Faster Parameterized Algorithms Using Linear Programming"],"prefix":"10.1145","volume":"11","author":[{"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[{"name":"University of California, San Diego"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"N. S.","family":"Narayanaswamy","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology, Madras"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[{"name":"Institute of Mathematical Sciences, Chennai"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[{"name":"Institute of Mathematical Sciences, Chennai"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"Institute of Mathematical Sciences, Chennai"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,10,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2027127.2027174"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00050-6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.06.026"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.03.026"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2462896.2462899"},{"key":"e_1_2_1_6_1","volume-title":"Fellows","author":"Downey Rod G.","year":"1999","unstructured":"Rod G. Downey and Michael R . Fellows . 1999 . Parameterized Complexity. Springer-Verlag , New York, NY. Rod G. Downey and Michael R. Fellows. 1999. Parameterized Complexity. Springer-Verlag, New York, NY."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9167-9"},{"key":"e_1_2_1_8_1","volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","unstructured":"J\u00f6rg Flum and Martin Grohe . 2006. Parameterized Complexity Theory . Springer-Verlag , Berlin, Germany . J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag, Berlin, Germany."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm056"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.02.001"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00177"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9393-4"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28050-4_11"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.46"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.09.003"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Daniel Lokshtanov Saket Saurabh and Somnath Sikdar. 2009. Simpler parameterized algorithm for OCT. In Combinatorial Algorithms. 380--384.  Daniel Lokshtanov Saket Saurabh and Somnath Sikdar. 2009. Simpler parameterized algorithm for OCT. In Combinatorial Algorithms. 380--384.","DOI":"10.1007\/978-3-642-10217-2_37"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0996"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.07.016"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9412-2"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580222"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580444"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01593772"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2040572.2040615"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.002"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2566616","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2566616","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:01:00Z","timestamp":1750230060000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2566616"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,30]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,11,17]]}},"alternative-id":["10.1145\/2566616"],"URL":"https:\/\/doi.org\/10.1145\/2566616","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,30]]},"assertion":[{"value":"2012-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}