{
  "id": "1603.09448",
  "version": "v1",
  "published": "2016-03-31T03:27:56.000Z",
  "updated": "2016-03-31T03:27:56.000Z",
  "title": "An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth",
  "authors": [
    "Zongwen Bai",
    "Jianhua Tu",
    "Yongtang Shi"
  ],
  "categories": [
    "math.CO",
    "cs.DS"
  ],
  "abstract": "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$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-03-31T03:27:56.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "bounded treewidth",
      "vertex graphs",
      "connected vertex cover",
      "real world",
      "dynamic programming algorithm"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2016arXiv160309448B"
    }
  }
}