<p>A more recent open list of problems can be seen in the open problem session videos of the 2019 Workshop on Kernelization (WorKer 2019) (<a href="https://youtu.be/vCjG5zGjQr4" rel="nofollow noreferrer">Session 1</a>, <a href="https://youtu.be/6ZlP_0cVBrg" rel="nofollow noreferrer">Session 2</a>).</p>
<p>Several of the problems mentioned already remain open:</p>
<ul>
<li>Directed Feedback Vertex Set and Planar Vertex Deletion parameterized
by the number <span class="math-container">$k$</span> of vertex deletions as mentioned by Bart remain
open.</li>
<li>The Interval Completion problem mentioned by Yixin remains open.</li>
</ul>
<p>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 <span class="math-container">$k$</span> edge deletions / modifications) parameterized by the solution size has a polynomial kernel.</p>

CC BY-SA 4.0
2020-10-13T20:52:07.883Z
2020-10-13T20:52:07.883Z
Christian Komusiewicz
<p>Currently, I would say the 3 major open cases are:</p>

<ol>
<li>Directed feedback vertex set (make a given digraph acyclic by deleting at most k vertices) parameterized by the size of the solution</li>
<li>Planar Vertex Deletion (make a graph planar by deleting at most k vertices)</li>
<li>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)</li>
</ol>

<p>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 ( <a href="http://worker2013.mimuw.edu.pl/slides/worker-opl.pdf">http://worker2013.mimuw.edu.pl/slides/worker-opl.pdf</a> ) for others. Pointers to other (but older) open problem lists in parameterized complexity can be found here: <a href="http://fpt.wikidot.com/open-problems">http://fpt.wikidot.com/open-problems</a> .</p>

CC BY-SA 3.0
2015-12-05T16:17:38.347Z
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.
Yixin Cao
CC BY-SA 3.0
2015-12-03T14:35:25.787Z
2015-12-03T14:35:25.787Z
Bart Jansen
<p>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 &quot;underline its hardness&quot;.</p>
<blockquote>
<p>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?</p>
</blockquote>
<p>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 <a href="http://arxiv.org/abs/1107.3068" rel="noreferrer">showed a randomized polynomial kernel for OCT</a>)</p>

<reference-request><big-list><parameterized-complexity><kernelization>
Major open problems on polynomial kernel (non) existence
Marzio De Biasi
# Major open problems on polynomial kernel (non) existence

(Asked by: username_0 on 2015-12-02)

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](http://arxiv.org/abs/1107.3068))

**Tags:** reference-request, big-list, parameterized-complexity, kernelization

---

## 2 answers

### Answer by username_2 on 2015-12-03. Score: 11 | Accepted answer

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> .

> **Comments:**
> **username_3**: 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.  

---

### Answer by username_1 on 2020-10-13. Score: 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](https://youtu.be/vCjG5zGjQr4), [Session 2](https://youtu.be/6ZlP_0cVBrg)).

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.


---

