An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth
Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 4
Voir la notice de l'article provenant de la source Episciences
Given a graph $G=(V,E)$ and a positive integer $t\geq2$, the task in the vertex cover $P_t$ ($VCP_t$) problem is to find a minimum subset of vertices $F\subseteq V$ such that every path of order $t$ in $G$ contains at least one vertex from $F$. The $VCP_t$ problem is NP-complete for any integer $t\geq2$ and has many applications in real world. Recently, the authors presented a dynamic programming algorithm running in time $4^p\cdot n^{O(1)}$ for the $VCP_3$ problem on $n$-vertex graphs with treewidth $p$. In this paper, we propose an improvement of it and improved the time-complexity to $3^p\cdot n^{O(1)}$. The connected vertex cover $P_3$ ($CVCP_3$) problem is the connected variation of the $VCP_3$ problem where $G[F]$ is required to be connected. Using the Cut\&Count technique, we give a randomized algorithm with runtime $4^p\cdot n^{O(1)}$ for the $CVCP_3$ problem on $n$-vertex graphs with treewidth $p$.
@article{DMTCS_2019_21_4_a15,
author = {Bai, Zongwen and Tu, Jianhua and Shi, Yongtang},
title = {An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth},
journal = {Discrete mathematics & theoretical computer science},
publisher = {mathdoc},
volume = {21},
number = {4},
year = {2019},
doi = {10.23638/DMTCS-21-4-17},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-17/}
}
TY - JOUR AU - Bai, Zongwen AU - Tu, Jianhua AU - Shi, Yongtang TI - An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth JO - Discrete mathematics & theoretical computer science PY - 2019 VL - 21 IS - 4 PB - mathdoc UR - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-17/ DO - 10.23638/DMTCS-21-4-17 LA - en ID - DMTCS_2019_21_4_a15 ER -
%0 Journal Article %A Bai, Zongwen %A Tu, Jianhua %A Shi, Yongtang %T An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth %J Discrete mathematics & theoretical computer science %D 2019 %V 21 %N 4 %I mathdoc %U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-17/ %R 10.23638/DMTCS-21-4-17 %G en %F DMTCS_2019_21_4_a15
Bai, Zongwen; Tu, Jianhua; Shi, Yongtang. An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth. Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 4. doi: 10.23638/DMTCS-21-4-17
Cité par Sources :