11
$\begingroup$

We are not able to settle the (non-)existence of a polynomial kernel for a parameterized combinatorial NP-complete problem (we also tried to apply some recent lower bound techniques to prove the non-existence of a polynomial kernel under reasonable complexity-theoretic assumptions). So we are searching for major open problems that could be used in a parameter-preserving reduction to "underline its hardness".

What are major parameterized NP-complete problems for which it is unknown if they have a polynomial kernel ? Is there a survey/technical report on the subject?

An example could be ODD CYCLE TRANSVERSAL (OCT), the task of making an undirected graph bipartite by deleting as few vertices as possible, parameterized by the number of allowed vertex deletions (though Stefan Kratsch and Magnus Wahlström recently showed a randomized polynomial kernel for OCT)

$\endgroup$
11
$\begingroup$

Currently, I would say the 3 major open cases are:

  1. Directed feedback vertex set (make a given digraph acyclic by deleting at most k vertices) parameterized by the size of the solution
  2. Planar Vertex Deletion (make a graph planar by deleting at most k vertices)
  3. Edge Multiway cut (given an undirected graph and a list of terminals, delete at most k edges to ensure all the terminals end up in a different connected component)

For all of these, the relevant parameter is the size of the solution. You can have a look at the open problem list from the 2013 Workshop on Kernelization ( http://worker2013.mimuw.edu.pl/slides/worker-opl.pdf ) for others. Pointers to other (but older) open problem lists in parameterized complexity can be found here: http://fpt.wikidot.com/open-problems .

$\endgroup$
1
  • 3
    $\begingroup$ I've two comments. 1. interval completion and interval vertex deletion are two other big names with poly-kernel open. 2, None of these five (3+2) problems seems to be good candidates for the study of nonexistence. $\endgroup$
    – Yixin Cao
    Dec 5 '15 at 16:17
2
$\begingroup$

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 Interval Completion problem mentioned by Yixin remains open.

One further, by now prominent, open problem is whether Claw-Free Deletion / Editing (decide whether we can make an undirected graph claw-free by at most $k$ edge deletions / modifications) parameterized by the solution size has a polynomial kernel.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.