2018/04/17 by Hung Le, Le, Hung, Baigong Zheng +1
Computer Science · #68W25 #68W40 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems #cs.DS #msc:68W25 #msc:68W40
paper · pdf · doi:10.48550/arxiv.1804.06428
12 page 1 figure, major revision
openalex publication_date 2018/04/17 · arxiv created 2019/06/02 · arxiv updated 2019/06/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that a simple local search gives a PTAS for the Feedback Vertex Set (FVS) problem in minor-free graphs. An efficient PTAS in minor-free graphs was known for this problem by Fomin, Lokshtanov, Raman and Sauraubh. However, their algorithm is a combination of many advanced algorithmic tools such as contraction decomposition framework introduced by Demaine and Hajiaghayi, Courcelle's theorem and the Robertson and Seymour decomposition. In stark contrast, our local search algorithm is very simple and easy to implement. It keeps exchanging a constant number of vertices to improve the current solution until a local optimum is reached. Our main contribution is to show that the local optimum only differs the global optimum by (1+ε) factor.