8
$\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$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.