On the Parameterized Complexity of Maximum Degree Contraction Problem

A simple brute-force algorithm that checks all possible sets of edges for a solution runs in time n^O(k).
As our first result, we prove that this algorithm is asymptotically optimal, up to constants in the exponents, under Exponential Time Hypothesis.

Belmonte, Golovach, van't Hof, and Paulusma studied the problem in the realm of Parameterized Complexity and proved, among other things, that it admits an FPT algorithm. We present a different FPT algorithm that runs significantly faster when d is a constant. In the same article, the authors asked whether the problem admits a polynomial kernel, when parameterized by k + d.
We answer this question in the negative and prove that it does not admit a polynomial compression unless NP is contained in coNP/poly.

--------------------
Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.