In Feedback Vertex Set, we are given an undirected graph $G$ and $k \in \mathbb{N}$, and the objective is to decide whether there exists a subset $S \subseteq V(G)$ of size at most $k$ such that $G-S$ is a forest. How can I solve it in running time complexity of $k^{O(\sqrt{k})} n^{O(1)}$ when restricted to planar graphs?

  • $\begingroup$ What are your thoughts? Where does this come up? $\endgroup$
    – vonbrand
    Jul 6 '21 at 10:51

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.