Years and Authors of Summarized Original Work
2012; Binkele-Raible, Fernau, Fomin, Lokshtanov, Saurabh
2013; Hermelin, Kratsch, Soltys, Wahlström, Wu
2014; Jansen
Definition and Discussion
The basic definition of the field expresses kernelization as a Karp (many-one) self-reduction. Classical complexity and recursion theory offers quite a lot of alternative and more general notions of reducibilities. The most general notion, that of a Turing reduction, motivates the following definition:
Let (Q, κ) be a parameterized problem over a finite alphabet \(\varSigma\).
An input-bounded oracle for (Q, κ) is an oracle that, for any given input \(x \in \varSigma ^{{\ast}}\) of (Q, κ) and any bound t, first checks if | x | , | κ(x) | ≤ t, and if this is certified, it decides in constant time whether the input x is a YES instance of (Q, κ).
A Turing kernelization (algorithm) for (Q, κ) is an algorithm that, provided with access to some input-bounded oracle for (Q, κ), decides on input \(x \in...
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Recommended Reading
Binkele-Raible D, Fernau H, Fomin FV, Lokshtanov D, Saurabh S, Villanger Y (2012) Kernel(s) for problems with no kernel: on out-trees with many leaves. ACM Trans Algorithms 8(4):38
Daligault J, Thomassé S (2009) On finding directed trees with many leaves. In: Chen J, Fomin FV (eds) Parameterized and exact computation, 4th international workshop, IWPEC, Copenhagen. LNCS, vol 5917. Springer, pp 86–97
Daligault J, Gutin G, Kim EJ, Yeo A (2010) FPT algorithms and kernels for the directed k-leaf problem. J Comput Syst Sci 76(2):144–152
Hermelin D, Kratsch S, Soltys K, Wahlström M, Wu X (2013) A completeness theory for polynomial (Turing) kernelization. In: Gutin G, Szeider S (eds) Parameterized and exact computation – 8th international symposium, IPEC, Sophia Antipolis. LNCS, vol 8246. Springer, pp 202–215
Jansen BMP (2014) Turing kernelization for finding long paths and cycles in restricted graph classes. Tech. Rep. 1402.4718v1, arXiv.CS.DS
Kammer F (2013) A linear-time kernelization for the rooted k-leaf outbranching problem. In: Brandstädt A, Jansen K, Reischuk R (eds) Graph-theoretic concepts in computer science – 39th international workshop, WG, Lübeck. LNCS, vol 8165. Springer, pp 310–320
Thomassé S, Trotignon N, Vuskovic K (2013) Parameterized algorithm for weighted independent set problem in bull-free graphs. CoRR abs/1310.6205, a conference version appeared at WG (LNCS volume) 2014
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer Science+Business Media New York
About this entry
Cite this entry
Fernau, H. (2016). Kernelization, Turing Kernels. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, New York, NY. https://doi.org/10.1007/978-1-4939-2864-4_528
Download citation
DOI: https://doi.org/10.1007/978-1-4939-2864-4_528
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4939-2863-7
Online ISBN: 978-1-4939-2864-4
eBook Packages: Computer ScienceReference Module Computer Science and Engineering