11

Currently, I would say the 3 major open cases are: Directed feedback vertex set (make a given digraph acyclic by deleting at most k vertices) parameterized by the size of the solution Planar Vertex Deletion (make a graph planar by deleting at most k vertices) Edge Multiway cut (given an undirected graph and a list of terminals, delete at most k edges to ...


5

Clearly there are similarities - both kernelization algorithms and Karp reductions need to work in polynomial time and produce an output instances that is equivalent to the input instance (in the sense that both are “yes”-instances or both are “no”-instances). But they are not the same concept, nor is one a special case of the other. First, they operate on ...


2

A more recent open list of problems can be seen in the open problem session videos of the 2019 Workshop on Kernelization (WorKer 2019) (Session 1, Session 2). Several of the problems mentioned already remain open: Directed Feedback Vertex Set and Planar Vertex Deletion parameterized by the number $k$ of vertex deletions as mentioned by Bart remain open. The ...


Only top voted, non community-wiki answers of a minimum length are eligible