An efficient polynomial time approximation scheme for the vertex cover P_ 3 problem on planar graphs
Yongtang Shi, Jianhua Tu · Discussiones Mathematicae Graph Theory · 2018
Given a graph G = (V, E), the task in the vertex cover P 3 (V CP 3 ) problem is to find a minimum subset of vertices F V such that every path of order 3 in G contains at least one vertex from F . The V CP 3 problem remains NP-hard even in planar graphs and has many applications in real world. In this paper, we give a dynamic-programming algorithm to solve the V CP 3 problem on graphs of bounded branchwidth. Using the dynamic programming algorithm and the Baker's EPTAS framework for NP-hard problems, we present an efficient polynomial time approximation scheme (EPTAS) for the V CP 3 problem on planar graphs.