Helsinki Algorithms Seminar: Syed Meesum, University of Wroclaw "Rank Vertex Cover as a Natural Problem for Algebraic Compression"

Rank Vertex Cover as a Natural Problem for Algebraic Compression

Syed Meesum
University of Wroclaw

The question of the existence of a polynomial kernelization of the Vertex Cover Above LP problem was a longstanding, notorious open problem in Parameterized Complexity. Six years ago, the breakthrough work by Kratsch and Wahlstr ̈om on representative sets finally answered this question in the affirmative [FOCS 2012]. In this talk, I will present an alternative, algebraic compression of the Vertex Cover Above LP problem into the Rank Vertex Cover problem. Here, the input consists of a graph G, a parameter k, and a bijection between V(G) and the set of columns of a representation of a matroid M, and the objective is to find a vertex cover whose rank is upper bounded by k.

Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.

Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.

For the season programme, please see the seminar webpage.