7
$\begingroup$

(This question also suits for other similar natural $\mathrm{NP}$-hard problems)

I know that there is a $4k^2$ vertex kernel (and $8k^2$ edge kernel) by Thomasse [Thomasse09] for Feedback Vertex Set (FVS) problem.

Harnik and Naor [HN06] introduced a notion of compression with the goal of succinctly storing instances of computational problems.

As argued by Dell and van Melkebeek [DV14], for every real number $\varepsilon > 0$, FVS does not admits a polynomial compression with bitsize $O(k^{2−\varepsilon})$, unless $\mathrm{NP} \subseteq \mathrm{coNP/poly}$. It shows that obtaining kernels for the FVS problems with a strictly subquadratic number of edges is implausible (since $O(k^{2−\varepsilon})$ edges can be encoded in $O(k^{2−\varepsilon}\log k)$ bits).

However, it seems hard to understand, using solely the notion of the compositions as a tool, whether obtaining a kernel for FVS with a subquadratic number of vertices is possible or not.

Is it possible that FVS has an $O(k^2/\log k)$ kernel? In general, if there do exist an $O(\mathrm{poly}(k))$ kernel for a natural (graph) problem and it has a lower bound of size $O(\mathrm{poly}(k))$ bit. Is it still possible that this problem has an $O(\mathrm{poly}(k)/\log k)$ kernel? Do we have any evidences or obversations to believe or doubt it?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.