Improved Approximation Algorithms for Path Vertex Covers in Regular Graphs View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2020-05-21

AUTHORS

An Zhang, Yong Chen, Zhi-Zhong Chen, Guohui Lin

ABSTRACT

Given a simple graph G=(V,E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G = (V, E)$$\end{document} and a constant integer k≥2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \ge 2$$\end{document}, the k-path vertex cover problem (PkVC) asks for a minimum subset F⊆V\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F \subseteq V$$\end{document} of vertices such that the induced subgraph G[V-F]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G[V - F]$$\end{document} does not contain any path of order k. When k=2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k = 2$$\end{document}, this turns out to be the classic vertex cover (VC) problem, which admits a 2-Θ1log|V|\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\left( 2 - {\Theta }\left( \frac{1}{\log |V|}\right) \right)$$\end{document}-approximation. The general PkVC admits a trivial k-approximation; when k=3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k = 3$$\end{document} and k=4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k = 4$$\end{document}, the best known approximation results are a 2-approximation and a 3-approximation, respectively. On d-regular graphs, the approximation ratios can be reduced to min2-5d+3+ϵ,2-(2-o(1))loglogdlogd\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\min \left\{ 2 - \frac{5}{d+3} + \epsilon , 2 - \frac{(2 - o(1))\log \log d}{\log d}\right\}$$\end{document} for VC (i.e., P2VC), 2-1d+4d-23d|V|\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2 - \frac{1}{d} + \frac{4d - 2}{3d |V|}$$\end{document} for P3VC, ⌊d/2⌋(2d-2)(⌊d/2⌋+1)(d-2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{\lfloor d/2\rfloor (2d - 2)}{(\lfloor d/2\rfloor + 1) (d - 2)}$$\end{document} for P4VC, and 2d-k+2d-k+2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{2d - k + 2}{d - k + 2}$$\end{document} for PkVC when 1≤k-2 More... »

PAGES

3041-3064

References to SciGraph publications

  • 2015-08-04. The k-Observer Problem on d-regular Graphs in STABILIZATION, SAFETY, AND SECURITY OF DISTRIBUTED SYSTEMS
  • 1995. On approximation properties of the Independent set problem for degree 3 graphs in ALGORITHMS AND DATA STRUCTURES
  • 2011-08-18. The K-observer problem in computer networks in NETWORKING SCIENCE
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00453-020-00717-3

    DOI

    http://dx.doi.org/10.1007/s00453-020-00717-3

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1127760134


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/11", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Medical and Health Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1117", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Public Health and Health Services", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Mathematics, Hangzhou Dianzi University, 350018, Hangzhou, China", 
              "id": "http://www.grid.ac/institutes/grid.411963.8", 
              "name": [
                "Department of Mathematics, Hangzhou Dianzi University, 350018, Hangzhou, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Zhang", 
            "givenName": "An", 
            "id": "sg:person.015273653637.29", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015273653637.29"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Mathematics, Hangzhou Dianzi University, 350018, Hangzhou, China", 
              "id": "http://www.grid.ac/institutes/grid.411963.8", 
              "name": [
                "Department of Mathematics, Hangzhou Dianzi University, 350018, Hangzhou, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chen", 
            "givenName": "Yong", 
            "id": "sg:person.010555136403.19", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010555136403.19"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Division of Information System Design, Tokyo Denki University, 350-0394, Saitama, Japan", 
              "id": "http://www.grid.ac/institutes/grid.412773.4", 
              "name": [
                "Division of Information System Design, Tokyo Denki University, 350-0394, Saitama, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chen", 
            "givenName": "Zhi-Zhong", 
            "id": "sg:person.015654265661.98", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, AB, Canada", 
              "id": "http://www.grid.ac/institutes/grid.17089.37", 
              "name": [
                "Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, AB, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lin", 
            "givenName": "Guohui", 
            "id": "sg:person.01130357621.02", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01130357621.02"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-319-21741-3_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012045709", 
              "https://doi.org/10.1007/978-3-319-21741-3_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s13119-011-0002-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004211150", 
              "https://doi.org/10.1007/s13119-011-0002-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-60220-8_84", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036888427", 
              "https://doi.org/10.1007/3-540-60220-8_84"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2020-05-21", 
        "datePublishedReg": "2020-05-21", 
        "description": "Given a simple graph G=(V,E)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$G = (V, E)$$\\end{document} and a constant integer k\u22652\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k \\ge 2$$\\end{document}, the k-path vertex cover problem (PkVC) asks for a minimum subset F\u2286V\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$F \\subseteq V$$\\end{document} of vertices such that the induced subgraph G[V-F]\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$G[V - F]$$\\end{document} does not contain any path of order k. When k=2\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k = 2$$\\end{document}, this turns out to be the classic vertex cover (VC) problem, which admits a 2-\u03981log|V|\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\left( 2 - {\\Theta }\\left( \\frac{1}{\\log |V|}\\right) \\right)$$\\end{document}-approximation. The general PkVC admits a trivial k-approximation; when k=3\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k = 3$$\\end{document} and k=4\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k = 4$$\\end{document}, the best known approximation results are a 2-approximation and a 3-approximation, respectively. On d-regular graphs, the approximation ratios can be reduced to min2-5d+3+\u03f5,2-(2-o(1))loglogdlogd\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\min \\left\\{ 2 - \\frac{5}{d+3} + \\epsilon , 2 - \\frac{(2 - o(1))\\log \\log d}{\\log d}\\right\\}$$\\end{document} for VC (i.e., P2VC), 2-1d+4d-23d|V|\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$2 - \\frac{1}{d} + \\frac{4d - 2}{3d |V|}$$\\end{document} for P3VC, \u230ad/2\u230b(2d-2)(\u230ad/2\u230b+1)(d-2)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\frac{\\lfloor d/2\\rfloor (2d - 2)}{(\\lfloor d/2\\rfloor + 1) (d - 2)}$$\\end{document} for P4VC, and 2d-k+2d-k+2\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\frac{2d - k + 2}{d - k + 2}$$\\end{document} for PkVC when 1\u2264k-2
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00453-020-00717-3'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00453-020-00717-3'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-020-00717-3'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-020-00717-3'


     

    This table displays all metadata directly associated to this object as RDF triples.

    142 TRIPLES      22 PREDICATES      65 URIs      54 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00453-020-00717-3 schema:about anzsrc-for:11
    2 anzsrc-for:1117
    3 schema:author N75a9e30118864a049ab4e621e26fd43f
    4 schema:citation sg:pub.10.1007/3-540-60220-8_84
    5 sg:pub.10.1007/978-3-319-21741-3_6
    6 sg:pub.10.1007/s13119-011-0002-7
    7 schema:datePublished 2020-05-21
    8 schema:datePublishedReg 2020-05-21
    9 schema:description Given a simple graph G=(V,E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G = (V, E)$$\end{document} and a constant integer k≥2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \ge 2$$\end{document}, the k-path vertex cover problem (PkVC) asks for a minimum subset F⊆V\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F \subseteq V$$\end{document} of vertices such that the induced subgraph G[V-F]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G[V - F]$$\end{document} does not contain any path of order k. When k=2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k = 2$$\end{document}, this turns out to be the classic vertex cover (VC) problem, which admits a 2-Θ1log|V|\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\left( 2 - {\Theta }\left( \frac{1}{\log |V|}\right) \right)$$\end{document}-approximation. The general PkVC admits a trivial k-approximation; when k=3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k = 3$$\end{document} and k=4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k = 4$$\end{document}, the best known approximation results are a 2-approximation and a 3-approximation, respectively. On d-regular graphs, the approximation ratios can be reduced to min2-5d+3+ϵ,2-(2-o(1))loglogdlogd\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\min \left\{ 2 - \frac{5}{d+3} + \epsilon , 2 - \frac{(2 - o(1))\log \log d}{\log d}\right\}$$\end{document} for VC (i.e., P2VC), 2-1d+4d-23d|V|\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2 - \frac{1}{d} + \frac{4d - 2}{3d |V|}$$\end{document} for P3VC, ⌊d/2⌋(2d-2)(⌊d/2⌋+1)(d-2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{\lfloor d/2\rfloor (2d - 2)}{(\lfloor d/2\rfloor + 1) (d - 2)}$$\end{document} for P4VC, and 2d-k+2d-k+2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{2d - k + 2}{d - k + 2}$$\end{document} for PkVC when 1≤k-2<d≤2(k-2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1 \le k-2 < d \le 2(k-2)$$\end{document}. By utilizing an existing algorithm for graph defective coloring, we first present a ⌊d/2⌋(2d-k+2)(⌊d/2⌋+1)(d-k+2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{\lfloor d/2\rfloor (2d - k + 2)}{(\lfloor d/2\rfloor + 1) (d - k + 2)}$$\end{document}-approximation for PkVC on d-regular graphs when 1≤k-2<d\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1 \le k - 2 < d$$\end{document}. This beats all the best known approximation results for PkVC on d-regular graphs for k≥3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \ge 3$$\end{document}, except for P4VC it ties with the best prior work and in particular they tie at 2 on cubic graphs and 4-regular graphs. We then propose a (1.875+ϵ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1.875 + \epsilon )$$\end{document}-approximation and a 1.852-approximation for P4VC on cubic graphs and 4-regular graphs, respectively. We also present a better approximation algorithm for P4VC on d-regular bipartite graphs.
    10 schema:genre article
    11 schema:inLanguage en
    12 schema:isAccessibleForFree true
    13 schema:isPartOf N1464b6a391aa49379f33ee5c9d0f9f24
    14 Na1ba3cfe09434318a788581cd4ad7cba
    15 sg:journal.1047644
    16 schema:keywords VC
    17 algorithm
    18 approximation
    19 approximation algorithm
    20 approximation ratio
    21 approximation results
    22 best approximation algorithm
    23 best prior work
    24 bipartite graphs
    25 classic vertex cover problem
    26 coloring
    27 constant integer
    28 cover
    29 cover problem
    30 cubic graphs
    31 defective coloring
    32 graph
    33 induced subgraph
    34 integers
    35 k-approximation
    36 k-path vertex cover problem
    37 minimum subset
    38 order k.
    39 path
    40 prior work
    41 problem
    42 ratio
    43 regular bipartite graphs
    44 regular graphs
    45 results
    46 simple graph
    47 subgraphs
    48 subset
    49 vertex cover
    50 vertex cover problem
    51 vertices
    52 work
    53 schema:name Improved Approximation Algorithms for Path Vertex Covers in Regular Graphs
    54 schema:pagination 3041-3064
    55 schema:productId N6f3e2d9d38fd485b90a129a6784c8bdd
    56 Ncefb989c2db14b1eae1b7e67b097edd6
    57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1127760134
    58 https://doi.org/10.1007/s00453-020-00717-3
    59 schema:sdDatePublished 2022-05-20T07:37
    60 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    61 schema:sdPublisher Nff7540a307bd456dad065ee983093242
    62 schema:url https://doi.org/10.1007/s00453-020-00717-3
    63 sgo:license sg:explorer/license/
    64 sgo:sdDataset articles
    65 rdf:type schema:ScholarlyArticle
    66 N1464b6a391aa49379f33ee5c9d0f9f24 schema:volumeNumber 82
    67 rdf:type schema:PublicationVolume
    68 N5d290890a62f4a1f93c79c0e18e9e5da rdf:first sg:person.01130357621.02
    69 rdf:rest rdf:nil
    70 N6b3b735cd83e46418d454c24496a3c8e rdf:first sg:person.015654265661.98
    71 rdf:rest N5d290890a62f4a1f93c79c0e18e9e5da
    72 N6f3e2d9d38fd485b90a129a6784c8bdd schema:name dimensions_id
    73 schema:value pub.1127760134
    74 rdf:type schema:PropertyValue
    75 N75a9e30118864a049ab4e621e26fd43f rdf:first sg:person.015273653637.29
    76 rdf:rest N9dc6a263826a4344bfff78114315860b
    77 N9dc6a263826a4344bfff78114315860b rdf:first sg:person.010555136403.19
    78 rdf:rest N6b3b735cd83e46418d454c24496a3c8e
    79 Na1ba3cfe09434318a788581cd4ad7cba schema:issueNumber 10
    80 rdf:type schema:PublicationIssue
    81 Ncefb989c2db14b1eae1b7e67b097edd6 schema:name doi
    82 schema:value 10.1007/s00453-020-00717-3
    83 rdf:type schema:PropertyValue
    84 Nff7540a307bd456dad065ee983093242 schema:name Springer Nature - SN SciGraph project
    85 rdf:type schema:Organization
    86 anzsrc-for:11 schema:inDefinedTermSet anzsrc-for:
    87 schema:name Medical and Health Sciences
    88 rdf:type schema:DefinedTerm
    89 anzsrc-for:1117 schema:inDefinedTermSet anzsrc-for:
    90 schema:name Public Health and Health Services
    91 rdf:type schema:DefinedTerm
    92 sg:grant.7538013 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-020-00717-3
    93 rdf:type schema:MonetaryGrant
    94 sg:grant.8124106 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-020-00717-3
    95 rdf:type schema:MonetaryGrant
    96 sg:grant.8132243 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-020-00717-3
    97 rdf:type schema:MonetaryGrant
    98 sg:grant.8898306 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-020-00717-3
    99 rdf:type schema:MonetaryGrant
    100 sg:journal.1047644 schema:issn 0178-4617
    101 1432-0541
    102 schema:name Algorithmica
    103 schema:publisher Springer Nature
    104 rdf:type schema:Periodical
    105 sg:person.010555136403.19 schema:affiliation grid-institutes:grid.411963.8
    106 schema:familyName Chen
    107 schema:givenName Yong
    108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010555136403.19
    109 rdf:type schema:Person
    110 sg:person.01130357621.02 schema:affiliation grid-institutes:grid.17089.37
    111 schema:familyName Lin
    112 schema:givenName Guohui
    113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01130357621.02
    114 rdf:type schema:Person
    115 sg:person.015273653637.29 schema:affiliation grid-institutes:grid.411963.8
    116 schema:familyName Zhang
    117 schema:givenName An
    118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015273653637.29
    119 rdf:type schema:Person
    120 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
    121 schema:familyName Chen
    122 schema:givenName Zhi-Zhong
    123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
    124 rdf:type schema:Person
    125 sg:pub.10.1007/3-540-60220-8_84 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036888427
    126 https://doi.org/10.1007/3-540-60220-8_84
    127 rdf:type schema:CreativeWork
    128 sg:pub.10.1007/978-3-319-21741-3_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012045709
    129 https://doi.org/10.1007/978-3-319-21741-3_6
    130 rdf:type schema:CreativeWork
    131 sg:pub.10.1007/s13119-011-0002-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004211150
    132 https://doi.org/10.1007/s13119-011-0002-7
    133 rdf:type schema:CreativeWork
    134 grid-institutes:grid.17089.37 schema:alternateName Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, AB, Canada
    135 schema:name Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, AB, Canada
    136 rdf:type schema:Organization
    137 grid-institutes:grid.411963.8 schema:alternateName Department of Mathematics, Hangzhou Dianzi University, 350018, Hangzhou, China
    138 schema:name Department of Mathematics, Hangzhou Dianzi University, 350018, Hangzhou, China
    139 rdf:type schema:Organization
    140 grid-institutes:grid.412773.4 schema:alternateName Division of Information System Design, Tokyo Denki University, 350-0394, Saitama, Japan
    141 schema:name Division of Information System Design, Tokyo Denki University, 350-0394, Saitama, Japan
    142 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...