On the vertex cover $$P_3$$ problem parameterized by treewidth |
| |
Authors: | Jianhua Tu Lidong Wu Jing Yuan Lei Cui |
| |
Institution: | 1.Department of Mathematics,Beijing University of Chemical Technology,Beijing,China;2.Department of Computer Science,The University of Texas at Tyler,Tyler,USA;3.Department of Computer Science,The University of Texas at Dallas,Richardson,USA |
| |
Abstract: | Consider a graph G. A subset of vertices, F, is called a vertex cover \(P_t\) (\(VCP_t\)) set if every path of order t contains at least one vertex in F. Finding a minimum \(VCP_t\) set in a graph is is NP-hard for any integer \(t\ge 2\) and is called the \(MVCP_3\) problem. In this paper, we study the parameterized algorithms for the \(MVCP_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}\cdot n^{O(1)}\) for the \(MVCP_3\) problem. Moreover, we show that for the \(MVCP_3\) problem on planar graphs, there is a subexponential parameterized algorithm running in time \(2^{O(\sqrt{k})}\cdot n^{O(1)}\) where k is the size of the optimal solution. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|