Skip to main content

Research Repository

Advanced Search

Kernelization Lower Bounds for Finding Constant-Size Subgraphs

Fluschnik, T.; Mertzios, G.B.; Nichterlein, A.

Kernelization Lower Bounds for Finding Constant-Size Subgraphs Thumbnail


Authors

T. Fluschnik

A. Nichterlein



Contributors

F. Manea
Editor

R. Miller
Editor

D. Nowotka
Editor

Abstract

Kernelization is an important tool in parameterized algorithmics. Given an input instance accompanied by a parameter, the goal is to compute in polynomial time an equivalent instance of the same problem such that the size of the reduced instance only depends on the parameter and not on the size of the original instance. In this paper, we provide a first conceptual study on limits of kernelization for several polynomial-time solvable problems. For instance, we consider the problem of finding a triangle with negative sum of edge weights parameterized by the maximum degree of the input graph. We prove that a linear-time computable strict kernel of truly subcubic size for this problem violates the popular APSP-conjecture.

Citation

Fluschnik, T., Mertzios, G., & Nichterlein, A. (2018). Kernelization Lower Bounds for Finding Constant-Size Subgraphs. In F. Manea, R. Miller, & D. Nowotka (Eds.), Sailing routes in the world of computation : 14th Conference on Computability in Europe, CiE 2018, Kiel, Germany, July 30-August 3, 2018. Proceedings (183-193). Springer Verlag. https://doi.org/10.1007/978-3-319-94418-0_19

Acceptance Date Apr 6, 2018
Online Publication Date Jul 3, 2018
Publication Date Jul 3, 2018
Deposit Date Sep 12, 2018
Publicly Available Date Sep 13, 2018
Publisher Springer Verlag
Pages 183-193
Series Title Lecture notes in computer science
Book Title Sailing routes in the world of computation : 14th Conference on Computability in Europe, CiE 2018, Kiel, Germany, July 30-August 3, 2018. Proceedings.
ISBN 9783319944173
DOI https://doi.org/10.1007/978-3-319-94418-0_19

Files





You might also like



Downloadable Citations