Meta-kernelization using Well-structured Modulators

Authors Eduard Eiben, Robert Ganian, Stefan Szeider



PDF
Thumbnail PDF

File

LIPIcs.IPEC.2015.114.pdf
  • Filesize: 436 kB
  • 13 pages

Document Identifiers

Author Details

Eduard Eiben
Robert Ganian
Stefan Szeider

Cite AsGet BibTex

Eduard Eiben, Robert Ganian, and Stefan Szeider. Meta-kernelization using Well-structured Modulators. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 114-126, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.IPEC.2015.114

Abstract

Kernelization investigates exact preprocessing algorithms with performance guarantees. The most prevalent type of parameters used in kernelization is the solution size for optimization problems; however, also structural parameters have been successfully used to obtain polynomial kernels for a wide range of problems. Many of these parameters can be defined as the size of a smallest modulator of the given graph into a fixed graph class (i.e., a set of vertices whose deletion puts the graph into the graph class). Such parameters admit the construction of polynomial kernels even when the solution size is large or not applicable. This work follows up on the research on meta-kernelization frameworks in terms of structural parameters. We develop a class of parameters which are based on a more general view on modulators: instead of size, the parameters employ a combination of rank-width and split decompositions to measure structure inside the modulator. This allows us to lift kernelization results from modulator-size to more general parameters, hence providing smaller kernels. We show (i) how such large but well-structured modulators can be efficiently approximated, (ii) how they can be used to obtain polynomial kernels for any graph problem expressible in Monadic Second Order logic, and (iii) how they allow the extension of previous results in the area of structural meta-kernelization.
Keywords
  • Kernelization
  • Parameterized complexity
  • Structural parameters
  • Rank-width
  • Split decompositions

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Noga Alon, Gregory Gutin, Eun Jung Kim, Stefan Szeider, and Anders Yeo. Solving max-r-sat above a tight lower bound. Algorithmica, 61(3):638-655, 2011. Google Scholar
  2. Stefan Arnborg, Bruno Courcelle, Andrzej Proskurowski, and Detlef Seese. An algebraic theory of graph reduction. J. of the ACM, 40(5):1134-1164, 1993. Google Scholar
  3. Ann Becker and Dan Geiger. Optimization of pearl’s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artif. Intell., 83(1):167-188, 1996. Google Scholar
  4. Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos. (meta) kernelization. In FOCS 2009, pages 629-638. IEEE Computer Society, 2009. Google Scholar
  5. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernel bounds for path and cycle problems. Theor. Comput. Sci., 511:117-136, 2013. Google Scholar
  6. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Preprocessing for treewidth: A combinatorial analysis through kernelization. SIAM J. Discrete Math., 27(4):2108-2142, 2013. Google Scholar
  7. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization lower bounds by cross-composition. SIAM J. Discrete Math., 28(1):277-305, 2014. Google Scholar
  8. Reinhard Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer Verlag, New York, 2nd edition, 2000. Google Scholar
  9. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer Verlag, 2013. Google Scholar
  10. Eduard Eiben, Robert Ganian, and Stefan Szeider. Solving problems on graphs of high rank-width. In Algorithms and Data Structures - 14th International Symposium, volume 9214 of Lecture Notes in Computer Science, pages 314-326. Springer, 2015. Google Scholar
  11. Fedor V. Fomin, Bart M. P. Jansen, and Michal Pilipczuk. Preprocessing subgraph and minor problems: When does a small vertex cover help? J. Comput. Syst. Sci., 80(2):468-495, 2014. Google Scholar
  12. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Bidimensionality and kernels. In SODA, pages 503-510, 2010. Google Scholar
  13. Jakub Gajarský, Petr Hliněný, Jan Obdržálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sanchez Villaamil, and Somnath Sikdar. Kernelization using structural parameters on sparse graph classes. In ESA 2013, volume 8125 of Lecture Notes in Computer Science, pages 529-540. Springer, 2013. Google Scholar
  14. Robert Ganian and Petr Hliněný. On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width. Discr. Appl. Math., 158(7):851-867, 2010. Google Scholar
  15. Robert Ganian, Friedrich Slivovsky, and Stefan Szeider. Meta-kernelization with structural parameters. In MFCS, pages 457-468, 2013. Google Scholar
  16. Petr Hliněný and Sang il Oum. Finding branch-decompositions and rank-decompositions. SIAM J. Comput., 38(3):1012-1032, 2008. Google Scholar
  17. Bart M. P. Jansen and Hans L. Bodlaender. Vertex cover kernelization revisited - upper and lower bounds for a refined parameter. Theory Comput. Syst., 53(2):263-299, 2013. Google Scholar
  18. Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar. Linear kernels and single-exponential algorithms via protrusion decompositions. In ICALP (1), pages 613-624, 2013. Google Scholar
  19. Leonid Libkin. Elements of Finite Model Theory. Springer, 2004. Google Scholar
  20. Jaroslav Nesetril and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and Combinatorics. Springer, 2012. Google Scholar
  21. Sang-il Oum and P. Seymour. Approximating clique-width and branch-width. J. Combin. Theory Ser. B, 96(4):514-528, 2006. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail