<p>In parameterized algorithms, we know there is a problem that</p>
<ol>
<li>has a subexponential parameterized algorithm (subexp for short) and a polynomial kernel (e.g., split edge deletion problem);</li>
<li>has no subexp, but has a polynomial kernel (e.g., paw-free edge deletion);</li>
<li>has no subexp and no polynomial kernel (e.g., <span class="math-container">$P_5$</span>-free edge deletion).</li>
</ol>
<p>So, <strong>is there an example that has subexp but has no polynomial kernel?</strong> (Now I consider a problem that has subexp, but I am not sure whether it admits a polynomial kernel.)
Or maybe some good references are talking about the relationship?</p>

CC BY-SA 4.0
2023-10-26T15:28:33.933Z
It is easy to create artificial examples by padding, e.g. the problem of finding a path of length $\sqrt{k}$ parameterized by $k$. I'll think about a natural example.
Laakeri
CC BY-SA 4.0
2023-10-31T08:35:57.113Z
@Laakeri Ok, thanks.
Hanchun Yuan
<parameterized-complexity>
What't the relationship between subexp and polynomial kenrel?
Hanchun Yuan
# What't the relationship between subexp and polynomial kenrel?

(Asked by: username_0 on 2023-10-26)

In parameterized algorithms, we know there is a problem that

1. has a subexponential parameterized algorithm (subexp for short) and a polynomial kernel (e.g., split edge deletion problem);
2. has no subexp, but has a polynomial kernel (e.g., paw-free edge deletion);
3. has no subexp and no polynomial kernel (e.g., $P\_5$-free edge deletion).

So, **is there an example that has subexp but has no polynomial kernel?** (Now I consider a problem that has subexp, but I am not sure whether it admits a polynomial kernel.)
Or maybe some good references are talking about the relationship?

**Tags:** parameterized-complexity
> **Comments:**
> **username_1**: It is easy to create artificial examples by padding, e.g. the problem of finding a path of length $\sqrt{k}$ parameterized by $k$. I'll think about a natural example.  
> **username_0**: @Laakeri Ok, thanks.  

---

## 0 answers

