{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,30]],"date-time":"2026-05-30T01:46:25Z","timestamp":1780105585128,"version":"3.54.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,1,8]],"date-time":"2019-01-08T00:00:00Z","timestamp":1546905600000},"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":[[2019,1,31]]},"abstract":"\n We consider four well-studied NP-complete packing\/covering problems on graphs: F\n eedback<\/jats:sc>\n V\n ertex<\/jats:sc>\n S\n et in<\/jats:sc>\n T\n ournaments<\/jats:sc>\n (FVST), C\n luster<\/jats:sc>\n V\n ertex<\/jats:sc>\n D\n eletion<\/jats:sc>\n (CVD), T\n riangle<\/jats:sc>\n P\n acking in<\/jats:sc>\n T\n ournaments<\/jats:sc>\n (TPT) and I\n nduced<\/jats:sc>\n P<\/jats:italic>\n 3<\/jats:sub>\n -P\n acking<\/jats:sc>\n . For these four problems, kernels with\n O<\/jats:italic>\n (\n k<\/jats:italic>\n 2<\/jats:sup>\n ) vertices have been known for a long time. In fact, such kernels can be obtained by interpreting these problems as finding either a packing of\n k<\/jats:italic>\n pairwise disjoint sets of size 3 (3-S\n et<\/jats:sc>\n P\n acking<\/jats:sc>\n ) or a hitting set of size at most\n k<\/jats:italic>\n for a family of sets of size at most 3 (3-H\n itting<\/jats:sc>\n S\n et<\/jats:sc>\n ). In this article, we give the first kernels for FVST, CVD, TPT, and I\n nduced<\/jats:sc>\n P<\/jats:italic>\n 3<\/jats:sub>\n -P\n acking<\/jats:sc>\n with a subquadratic number of vertices. Specifically, we obtain the following results.\n <\/jats:p>\n \n \u2022 FVST admits a kernel with\n O<\/jats:italic>\n (\n k<\/jats:italic>\n 3\/2<\/jats:sup>\n ) vertices.\n <\/jats:p>\n \n \u2022 CVD admits a kernel with\n O<\/jats:italic>\n (\n k<\/jats:italic>\n 5\/3<\/jats:sup>\n ) vertices.\n <\/jats:p>\n \n \u2022 TPT admits a kernel with\n O<\/jats:italic>\n (\n k<\/jats:italic>\n 3\/2<\/jats:sup>\n ) vertices.\n <\/jats:p>\n \n \u2022 I\n nduced<\/jats:sc>\n P<\/jats:italic>\n 3<\/jats:sub>\n -P\n acking<\/jats:sc>\n admits a kernel with\n O<\/jats:italic>\n (\n k<\/jats:italic>\n 5\/3<\/jats:sup>\n ) vertices.\n <\/jats:p>\n \n Our results resolve an open problem from WorKer 2010 on the existence of kernels with O(\n k<\/jats:italic>\n 2\u2212\u03f5<\/jats:sup>\n ) vertices for FVST and CVD. All of our results are based on novel uses of old and new \u201cexpansion lemmas\u201d and a weak form of crown decomposition where (i)\n almost all<\/jats:italic>\n of the head is used by the solution (as opposed to\n all<\/jats:italic>\n ), (ii)\n almost none<\/jats:italic>\n of the crown is used by the solution (as opposed to\n none<\/jats:italic>\n ), and (iii) if\n H<\/jats:italic>\n is removed from\n G<\/jats:italic>\n , then there is\n almost no<\/jats:italic>\n interaction between the head and the rest (as opposed to\n no<\/jats:italic>\n interaction at all).\n <\/jats:p>","DOI":"10.1145\/3293466","type":"journal-article","created":{"date-parts":[[2019,1,8]],"date-time":"2019-01-08T15:53:12Z","timestamp":1546962792000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Subquadratic Kernels for Implicit 3-H\n itting<\/scp>\n S\n et<\/scp>\n and 3-S\n et<\/scp>\n P\n acking<\/scp>\n Problems"],"prefix":"10.1145","volume":"15","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[{"name":"University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tien-Nam","family":"Le","sequence":"additional","affiliation":[{"name":"\u00c9cole Normale Sup\u00e9rieure de Lyon, Lyon, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"University of Bergen, Norway and The Institute of Mathematical Sciences, HBNI, Chennai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"St\u00e9phan","family":"Thomass\u00e9","sequence":"additional","affiliation":[{"name":"\u00c9cole Normale Sup\u00e9rieure de Lyon, Lyon, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[{"name":"Ben-Gurion University, Beersheba, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,1,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.04.020"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.09.002"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 25th Annual European Symposium on Algorithms (ESA\u201917)","author":"Bessy S.","unstructured":"S. Bessy , M. Bougeret , and J. Thiebaut . 2017. Triangle packing in (sparse) tournaments: Approximation and kernelization . In Proceedings of the 25th Annual European Symposium on Algorithms (ESA\u201917) . 4:1--14:13. S. Bessy, M. Bougeret, and J. Thiebaut. 2017. Triangle packing in (sparse) tournaments: Approximation and kernelization. In Proceedings of the 25th Annual European Symposium on Algorithms (ESA\u201917). 4:1--14:13."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.10.001"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"e_1_2_1_6_1","volume-title":"WORKER 2010","author":"Bodlaender Hans L.","year":"2010","unstructured":"Hans L. Bodlaender , Fedor V. Fomin , and Saket Saurabh . 2010 . Open problems , WORKER 2010 . Retrieved November 27, 2018 from http:\/\/fpt.wikidot.com\/open-problems (2010). Hans L. Bodlaender, Fedor V. Fomin, and Saket Saurabh. 2010. Open problems, WORKER 2010. Retrieved November 27, 2018 from http:\/\/fpt.wikidot.com\/open-problems (2010)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-015-9631-7"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798338163"},{"key":"e_1_2_1_9_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 , New York, NY . Marek Cygan, Fedor V. Fomin, \u0141ukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Micha\u0142 Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer, New York, NY."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095122"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629620"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2009.08.001"},{"key":"e_1_2_1_13_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"2013","unstructured":"Rodney G. Downey and Michael R . Fellows . 2013 . Fundamentals of Parameterized Complexity. Springer , New York, NY. Rodney G. Downey and Michael R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer, New York, NY."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/130927115"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1409020.1409024"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-33461-5_20"},{"key":"e_1_2_1_17_1","volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","unstructured":"J\u00f6rg Flum and Martin Grohe . 2006. Parameterized Complexity Theory . Springer , Berlin . 493 pages. J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer, Berlin. 493 pages."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897551"},{"key":"e_1_2_1_19_1","volume-title":"Fomin and Saket Saurabh","author":"Fedor","year":"2014","unstructured":"Fedor V. Fomin and Saket Saurabh . 2014 . Kernelization methods for fixed-parameter tractability. In Tractability. Cambridge University Press , Cambridge, UK, 260--282. Fedor V. Fomin and Saket Saurabh. 2014. Kernelization methods for fixed-parameter tractability. In Tractability. Cambridge University Press, Cambridge, UK, 260--282."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.007"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233481.1233493"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9910-8"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095125"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9150-x"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915)","author":"Bart M.","year":"2015","unstructured":"Bart M. P. Jansen and D\u00e1niel Marx. 2015. Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels . In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915) , San Diego, CA, USA , January 4-6, 2015 . 616--629. Bart M. P. Jansen and D\u00e1niel Marx. 2015. Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915), San Diego, CA, USA, January 4-6, 2015. 616--629."},{"key":"e_1_2_1_27_1","volume-title":"Recent developments in kernelization: A survey. Bulletin of the EATCS 113","author":"Kratsch Stefan","year":"2014","unstructured":"Stefan Kratsch . 2014. Recent developments in kernelization: A survey. Bulletin of the EATCS 113 ( 2014 ). http:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/285 Stefan Kratsch. 2014. Recent developments in kernelization: A survey. Bulletin of the EATCS 113 (2014). http:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/285"},{"key":"e_1_2_1_28_1","volume-title":"33rd Symposium on Theoretical Aspects of Computer Science (STACS\u201916)","volume":"47","author":"Kumar Mithilesh","year":"2016","unstructured":"Mithilesh Kumar and Daniel Lokshtanov . 2016 . Faster exact and parameterized algorithm for feedback vertex set in tournaments . In 33rd Symposium on Theoretical Aspects of Computer Science (STACS\u201916) , February 17-20, 2016, Orl\u00e9ans, France (LIPIcs) , Vol. 47 . 49:1--49:13. Mithilesh Kumar and Daniel Lokshtanov. 2016. Faster exact and parameterized algorithm for feedback vertex set in tournaments. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS\u201916), February 17-20, 2016, Orl\u00e9ans, France (LIPIcs), Vol. 47. 49:1--49:13."},{"key":"e_1_2_1_29_1","volume-title":"The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday","author":"Lokshtanov Daniel","unstructured":"Daniel Lokshtanov , Neeldhara Misra , and Saket Saurabh . 2012. Kernelization - Preprocessing with a guarantee . In The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday . Springer-Verlag Berlin Heidelberg , Germany , 129--161. Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. 2012. Kernelization - Preprocessing with a guarantee. In The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. Springer-Verlag Berlin Heidelberg, Germany, 129--161."},{"key":"e_1_2_1_30_1","volume-title":"24th Annual European Symposium on Algorithms (ESA\u201916)","volume":"57","author":"Mnich Matthias","year":"2016","unstructured":"Matthias Mnich , Virginia Vassilevska Williams , and L\u00e1szl\u00f3 A. V\u00e9gh . 2016. A 7\/3-approximation for feedback vertex sets in tournaments . In 24th Annual European Symposium on Algorithms (ESA\u201916) , August 22-24, 2016 , Aarhus, Denmark (LIPIcs) , Vol. 57 . 67:1--67:14. Matthias Mnich, Virginia Vassilevska Williams, and L\u00e1szl\u00f3 A. V\u00e9gh. 2016. A 7\/3-approximation for feedback vertex sets in tournaments. In 24th Annual European Symposium on Algorithms (ESA\u201916), August 22-24, 2016, Aarhus, Denmark (LIPIcs), Vol. 57. 67:1--67:14."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-95891-8_37"},{"key":"e_1_2_1_32_1","volume-title":"Invitation to Fixed-Parameter Algorithms. Oxford Lecture series in Mathematics and its Applications","author":"Niedermeier Rolf","unstructured":"Rolf Niedermeier . 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture series in Mathematics and its Applications , Vol. 31 . Oxford University Press , Oxford, UK . Rolf Niedermeier. 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture series in Mathematics and its Applications, Vol. 31. Oxford University Press, Oxford, UK."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721848"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2016.11.007"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3293466","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3293466","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:01Z","timestamp":1750208521000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3293466"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,8]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1,31]]}},"alternative-id":["10.1145\/3293466"],"URL":"https:\/\/doi.org\/10.1145\/3293466","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,8]]},"assertion":[{"value":"2018-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}