{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,9,25]],"date-time":"2022-09-25T06:26:56Z","timestamp":1664087216061},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"Rigorous Theory of Preprocessing","award":["267959"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2012,9]]},"abstract":"\n The\n k<\/jats:italic>\n -Leaf Out-Branching problem is to find an out-branching, that is a rooted oriented spanning tree, with at least\n k<\/jats:italic>\n leaves in a given digraph. The problem has recently received much attention from the viewpoint of parameterized algorithms. Here, we take a kernelization based approach to the\n k<\/jats:italic>\n -Leaf-Out-Branching problem. We give the first polynomial kernel for Rooted\n k<\/jats:italic>\n -Leaf-Out-Branching, a variant of\n k<\/jats:italic>\n -Leaf-Out-Branching where the root of the tree searched for is also a part of the input. Our kernel with\n O<\/jats:italic>\n (\n k<\/jats:italic>\n 3<\/jats:sup>\n ) vertices is obtained using extremal combinatorics.\n <\/jats:p>\n \n For the\n k<\/jats:italic>\n -Leaf-Out-Branching problem, we show that no polynomial-sized kernel is possible unless\n coNP<\/jats:italic>\n is in\n NP\/poly<\/jats:italic>\n . However, our positive results for Rooted\n k<\/jats:italic>\n -Leaf-Out-Branching immediately imply that the seemingly intractable\n k<\/jats:italic>\n -Leaf-Out-Branching problem admits a data reduction to\n n<\/jats:italic>\n independent polynomial-sized kernels. These two results, tractability and intractability side by side, are the first ones separating\n Karp kernelization<\/jats:italic>\n from\n Turing kernelization<\/jats:italic>\n . This answers affirmatively an open problem regarding \u201ccheat kernelization\u201d raised by Mike Fellows and Jiong Guo independently.\n <\/jats:p>","DOI":"10.1145\/2344422.2344428","type":"journal-article","created":{"date-parts":[[2012,10,2]],"date-time":"2012-10-02T13:50:00Z","timestamp":1349185800000},"page":"1-19","source":"Crossref","is-referenced-by-count":29,"title":["Kernel(s) for problems with no kernel"],"prefix":"10.1145","volume":"8","author":[{"given":"Daniel","family":"Binkele-Raible","sequence":"first","affiliation":[{"name":"Universit\u00e4t Trier, Germany"}]},{"given":"Henning","family":"Fernau","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Trier, Germany"}]},{"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[{"name":"University of Bergen, Bergen, Norway"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"University of Bergen, Bergen, Norway"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences, Chennai, India"}]},{"given":"Yngve","family":"Villanger","sequence":"additional","affiliation":[{"name":"University of Bergen, Bergen, Norway"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/070710494"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 34th International Coloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science","volume":"4596","author":"Alon N."},{"key":"e_1_2_1_3_1","unstructured":"Binkele-Raible D.\n and \n \n \n Fernau H\n \n \n . \n 2012\n . A faster exact algorithm for the directed maximum leaf spanning tree problem. In Computer Science in Russia CSR Lecture Notes in Computer Science vol. \n 6072\n . \n Springer 328--339. 10.1007\/978-3-642-13182-0_31 Binkele-Raible D. and Fernau H. 2012. A faster exact algorithm for the directed maximum leaf spanning tree problem. In Computer Science in Russia CSR Lecture Notes in Computer Science vol. 6072. Springer 328--339. 10.1007\/978-3-642-13182-0_31"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_2"},{"key":"e_1_2_1_5_1","volume-title":"Tech. Rep. UU-CS-2008-017, Department of Informatics and Computing Sciences","author":"Bodlaender H. L.","year":"2008"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1747997"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the Mathematical Foundations of Computer Science 2003 (MFCS). Lecture Notes in Computer Science","volume":"2747","author":"Bonsma P. S."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_19"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/050646354"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1186"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.06.005"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_7"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806725"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Ding G. Johnson T. and Seymour P. 2001. Spanning trees with many leaves. J. Graph Theory 189--197. 10.1002\/jgt.v37:4 Ding G. Johnson T. and Seymour P. 2001. Spanning trees with many leaves. J. Graph Theory 189--197. 10.1002\/jgt.v37:4","DOI":"10.1002\/jgt.1013"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer. Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1798596.1798599"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the Symposium of Algorithms and Complexity in Durham (ACiD","volume":"4","author":"Estivill-Castro V.","year":"2005"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11847250_25"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 20th Conference Foundations of Software Technology and Theoretical Computer Science (FST TCS). Lecture Notes in Computer Science","volume":"1974","author":"Fellows M. R."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS). Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Germany, 421--432","author":"Fernau H."},{"key":"e_1_2_1_22_1","unstructured":"Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Text in Theoretical Computer Science. Springer. Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Text in Theoretical Computer Science. Springer."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9145-z"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA","author":"Fomin F. V.","year":"2010"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90139-2"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130604"},{"key":"e_1_2_1_27_1","unstructured":"Griggs J. R. and Wu M. 1992. Spanning trees in graphs of minimum degree four or five. Disc. Math. 104. 10.1016\/0012-365X(92)90331-9 Griggs J. R. and Wu M. 1992. Spanning trees in graphs of minimum degree four or five. Disc. Math. 104. 10.1016\/0012-365X(92)90331-9"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233481.1233493"},{"key":"e_1_2_1_29_1","volume-title":"Complexity of Computer Computations","author":"Karp R. M."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404010"},{"key":"e_1_2_1_31_1","unstructured":"Kneis J. Langer A. and \n \n \n Rossmanith P\n \n \n . \n 2008\n . A new algorithm for finding trees with many leaves. In Algorithms and Computation ISAAC Lecture Notes in Computer Science vol. \n 5369\n . \n Springer 270--281. 10.1007\/978-3-540-92182-0_26 Kneis J. Langer A. and Rossmanith P. 2008. A new algorithm for finding trees with many leaves. In Algorithms and Computation ISAAC Lecture Notes in Computer Science vol. 5369. Springer 270--281. 10.1007\/978-3-540-92182-0_26"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0944"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Niedermeier R. 2006. Invitation to Fixed-Parameter Algorithms. Oxford University Press. Niedermeier R. 2006. Invitation to Fixed-Parameter Algorithms. Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2012.03.006"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/647908.739992"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721848"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2344422.2344428","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,28]],"date-time":"2021-02-28T18:52:02Z","timestamp":1614538322000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2344422.2344428"}},"subtitle":["On out-trees with many leaves"],"short-title":[],"issued":{"date-parts":[[2012,9]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,9]]}},"alternative-id":["10.1145\/2344422.2344428"],"URL":"http:\/\/dx.doi.org\/10.1145\/2344422.2344428","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":["Mathematics (miscellaneous)"],"published":{"date-parts":[[2012,9]]}}}