Designing Practical PTASes for Minimum Feedback Vertex Set in Planar Graphs

Glencora Borradaile, Hung Le, Baigong Zheng

We present two algorithms for the minimum feedback vertex set problem in planar graphs: an $O(n\log n)$ PTAS using a linear kernel and balanced separator, and a heuristic algorith…