7
$\begingroup$

We are not able to settle the (non) existence of a polynomial kernel for a parametrized 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 parametrized 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, parametrized by the number of allowed vertex deletions (though Stefan Kratsch and Magnus Wahlström recently showed a randomized polynomial kernel for OCT)

$\endgroup$
7
$\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$
  • $\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

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.