On the vertex cover P3 problem parameterized by treewidth

Consider a graph G. A subset of vertices, F, is called a vertex cover $P_t$ ( $VC{P}_t$ ) set if every path of order t contains at least one vertex in F. Finding a minimum $VC{P}_t$ set in a graph is is NP‐hard for any integer $t\ge 2$ and is called the $MVC{P}_3$ problem. In this paper, we study the parameterized algorithms for the $MVC{P}_3$ problem when the underlying graph G is parameterized by the treewidth. Given an n‐vertex graph together with its tree decomposition of width at most p, we present an algorithm running in time $4^p·n^{O(1)}$ for the $MVC{P}_3$ problem. Moreover, we show that for the $MVC{P}_3$ problem on planar graphs, there is a subexponential parameterized algorithm running in time $2^{O(\sqrt{k})}·n^{O(1)}$ where k is the size of the optimal solution.