{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2021,3,9]],"date-time":"2021-03-09T21:45:34Z","timestamp":1615326334890},"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":26,"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":"10.1137\/070710494","doi-asserted-by":"publisher"},{"key":"e_1_2_1_2_1","author":"Alon N.","volume":"4596","volume-title":"Proceedings of the 34th International Coloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science"},{"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":"10.1007\/978-3-642-11269-0_2","doi-asserted-by":"publisher"},{"key":"e_1_2_1_5_1","author":"Bodlaender H. L.","year":"2008","volume-title":"Tech. Rep. UU-CS-2008-017, Department of Informatics and Computing Sciences"},{"key":"e_1_2_1_6_1","DOI":"10.1016\/j.jcss.2009.04.001","doi-asserted-by":"publisher"},{"key":"e_1_2_1_7_1","DOI":"10.5555\/1747597.1747997","doi-asserted-by":"publisher"},{"key":"e_1_2_1_8_1","author":"Bonsma P. S.","volume":"2747","volume-title":"Proceedings of the Mathematical Foundations of Computer Science 2003 (MFCS). Lecture Notes in Computer Science"},{"key":"e_1_2_1_9_1","DOI":"10.1007\/978-3-540-87744-8_19","doi-asserted-by":"publisher"},{"key":"e_1_2_1_10_1","DOI":"10.1137\/050646354","doi-asserted-by":"publisher"},{"key":"e_1_2_1_11_1","DOI":"10.1006\/jagm.2001.1186","doi-asserted-by":"publisher"},{"key":"e_1_2_1_12_1","DOI":"10.1016\/j.jcss.2009.06.005","doi-asserted-by":"publisher"},{"key":"e_1_2_1_13_1","DOI":"10.1007\/978-3-642-11269-0_7","doi-asserted-by":"publisher"},{"key":"e_1_2_1_14_1","DOI":"10.1145\/1806689.1806725","doi-asserted-by":"publisher"},{"key":"e_1_2_1_15_1","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","doi-asserted-by":"crossref"},{"key":"e_1_2_1_16_1","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","doi-asserted-by":"crossref"},{"key":"e_1_2_1_17_1","DOI":"10.1145\/1798596.1798599","doi-asserted-by":"publisher"},{"key":"e_1_2_1_18_1","author":"Estivill-Castro V.","volume":"4","year":"2005","volume-title":"Proceedings of the Symposium of Algorithms and Complexity in Durham (ACiD"},{"key":"e_1_2_1_19_1","DOI":"10.1007\/11847250_25","doi-asserted-by":"publisher"},{"key":"e_1_2_1_20_1","author":"Fellows M. R.","volume":"1974","volume-title":"Proceedings of the 20th Conference Foundations of Software Technology and Theoretical Computer Science (FST TCS). Lecture Notes in Computer Science"},{"key":"e_1_2_1_21_1","author":"Fernau H.","volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS). Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Germany, 421--432"},{"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":"10.1007\/s00453-007-9145-z","doi-asserted-by":"publisher"},{"key":"e_1_2_1_24_1","author":"Fomin F. V.","year":"2010","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA"},{"key":"e_1_2_1_25_1","DOI":"10.1016\/0020-0190(94)90139-2","doi-asserted-by":"publisher"},{"key":"e_1_2_1_26_1","DOI":"10.1002\/jgt.3190130604","doi-asserted-by":"publisher"},{"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":"10.1145\/1233481.1233493","doi-asserted-by":"publisher"},{"key":"e_1_2_1_29_1","author":"Karp R. M.","volume-title":"Complexity of Computer Computations"},{"key":"e_1_2_1_30_1","DOI":"10.1137\/0404010","doi-asserted-by":"publisher"},{"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":"10.1006\/jagm.1998.0944","doi-asserted-by":"publisher"},{"key":"e_1_2_1_33_1","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","doi-asserted-by":"crossref"},{"key":"e_1_2_1_34_1","DOI":"10.1016\/j.jda.2012.03.006","doi-asserted-by":"publisher"},{"key":"e_1_2_1_35_1","DOI":"10.5555\/647908.739992","doi-asserted-by":"publisher"},{"key":"e_1_2_1_36_1","DOI":"10.1145\/1721837.1721848","doi-asserted-by":"publisher"}],"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.0,"subtitle":["On out-trees with many leaves"],"short-title":[],"issued":{"date-parts":[[2012,9]]},"references-count":36,"journal-issue":{"published-print":{"date-parts":[[2012,9]]},"issue":"4"},"alternative-id":["10.1145\/2344422.2344428"],"URL":"http:\/\/dx.doi.org\/10.1145\/2344422.2344428","relation":{"cites":[]},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}]}}