A Retrospective on (Meta) Kernelization
| Autor: | Dimitrios M. Thilikos |
|---|---|
| Přispěvatelé: | Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), ANR-16-CE40-0028,DE-MO-GRAPH,Décomposition de Modèles Graphiques(2016), ANR-17-CE23-0010,ESIGMA,Efficacité et structure pour les applications de la fouille de graphes(2017) |
| Rok vydání: | 2020 |
| Předmět: |
Polynomial
Theoretical computer science Reduction (recursion theory) Computer science Treewidth Bidimensionality [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] Separability Parameterized complexity 0102 computer and information sciences Parameterized problems 01 natural sciences Algorithmics Kernelization Algorithms Preprocessor Protrusion Decompositions 0101 mathematics Algorithmic Meta-theorems Finite Index Parameterized Algorithms 010102 general mathematics Finite Integer Index Monadic Second Order Logic 010201 computation theory & mathematics Kernelization |
| Zdroj: | Treewidth, Kernels, and Algorithms ISBN: 9783030420703 Treewidth, Kernels, and Algorithms Treewidth, Kernels, and Algorithms, 12160, pp.222-246, 2020, Lecture Notes in Computer Science, 978-3-030-42070-3. ⟨10.1007/978-3-030-42071-0_16⟩ |
| Popis: | International audience; In parameterized complexity, a {\em kernelization algorithm} can be seen as a reduction of a parameterized problem to itself, so that the produced equivalent instance has size depending exclusively on the parameter. If this size is polynomial, then then we say that the parameterized problem in question admits a polynomial kernelization algorithm. Kernelization can be seen as a formalization of the notion of preprocessingand has occupied a big part of the research on Multi-variate Algorithmics. The first algorithmic meta-theorem on kernelizationappeared in \href{https://arxiv.org/pdf/0904.0727}{\green{[{\sl H.~L. Bodlaender, F.~V. Fomin, D.~Lokshtanov, E.~Penninkx, S.~Saurabh, and D.~M. Thilikos. (Meta) kernelization. J. {ACM}, 63(5):44:1--44:69, 2016}\,]}} and unified a large family of previously known kernelization results on problems defined on topologically embeddable graphs.In this exposition we present the central results of this paper. During our presentation we pay attention to the abstractions on which the results where founded and take into account the subsequent advancements on this topic. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|