Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Kernelization lower bounds for finding constant-size subgraphs.

Fluschnik, T. and Mertzios, G.B. and Nichterlein, A. (2018) 'Kernelization lower bounds for finding constant-size subgraphs.', in Sailing routes in the world of computation : 14th Conference on Computability in Europe, CiE 2018, Kiel, Germany, July 30-August 3, 2018. Proceedings. Cham: Springer, pp. 183-193. Lecture notes in computer science. (10936).

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.

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Download PDF
(490Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1007/978-3-319-94418-0_19
Publisher statement:This is a post-peer-review, pre-copyedit version of an article published in Lecture Notes in Computer Science. The final authenticated version is available online at: https://doi.org/10.1007/978-3-319-94418-0_19
Date accepted:06 April 2018
Date deposited:13 September 2018
Date of first online publication:03 July 2018
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar