2015 | OriginalPaper | Buchkapitel
Lower bounds for kernelization
verfasst von : Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
Erschienen in: Parameterized Algorithms
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this chapter we discuss methodologies for proving lower bounds for kernelization. We describe the technique of compositionality, which is the main tool for proving negative results about the existence of polynomial kernels. We also give an introduction to weak compositions, which can be used to provide more precise lower bounds on kernel sizes.