# Improved Approximation Algorithms for Path Vertex Covers in Regular Graphs

Ontology type: schema:ScholarlyArticle      Open Access: True

### Article Info

DATE

2020-05-21

AUTHORS 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

TITLE

Algorithmica

ISSUE

10

VOLUME

82

### 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:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"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:  HOW TO GET THIS DATA PROGRAMMATICALLY: JSON-LD N-Triples Turtle RDF/XML 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) ... 
 function OptanonWrapper() { } SN SciGraph Explorer      |     © Springer Nature 2017-2022      |     Quicklinks:   Getting Started  |  Downloads      |     Cookie Settings // make tabs persistent // https://stackoverflow.com/questions/9685968/best-way-to-make-twitter-bootstrap-tabs-persistent $(document).ready(function() { // show active tab on reload if (location.hash !== '')$('a[href="' + location.hash + '"]').tab('show'); // remember the hash in the URL without jumping $('a[data-toggle="tab"]').on('shown.bs.tab', function(e) { if(history.pushState) { history.pushState(null, null, '#'+$(e.target).attr('href').substr(1)); } else { location.hash = '#'+$(e.target).attr('href').substr(1); } }); }); // Enable tooltips everywhere$(function () { $('[data-toggle="tooltip"]').tooltip({ 'html' : true , }) }) // TABS CONTROLLER // use to load viz when tab is clicked var viz_first_time = true;$('#topTabs a[data-toggle=tab]').on('shown.bs.tab', function (e){ //e.preventDefault(); var target = $(e.target).attr("href"); console.log('Tab: ' + target); if (target == '#tabvisual') { if (viz_first_time) { console.log('Rendering dataviz..'); render_viz('mynetwork', nodeData, edgeData); viz_first_time = false; } }$(this).tab('show'); }); // SLIDE REVEAL // USE WITH: slider.slideReveal("show"); var slider = $('#slider').slideReveal({ push: true, overlay: false, width: 600, speed: 700 }); // legacy function resize(size) { // expand/collapse div with graph if (size == "compact") { if ($("#overview_graph_div").hasClass("col-md-12")) { $("#overview_graph_div").removeClass("col-md-12").addClass("col-md-6");$("#details_div").removeClass("col-md-12").addClass("col-md-6"); $("#compact_button").addClass("active");$("#wide_button").removeClass("active"); } } else if (size == "wide") { if ($("#overview_graph_div").hasClass("col-md-6")) {$("#overview_graph_div").removeClass("col-md-6").addClass("col-md-12"); $("#details_div").removeClass("col-md-6").addClass("col-md-12");$("#wide_button").addClass("active"); $("#compact_button").removeClass("active"); } } } function render_viz(container) { // create a network var container = document.getElementById(container); // provide the data in the vis format var data = { nodes: nodes, edges: edges }; // initialize your network! var network = new vis.Network(container, data, options); network.on('click', actionPreviewRdf); network.on('doubleClick', actionJumpPage); network.fit(); } var bclick=false; function actionPreviewRdf(data) { data.event.preventDefault(); if (data.nodes) { // console.log(data.nodes); var thisnode_id = data.nodes[0]; // assuming one node is clicked at a time! var node = nodes.get(thisnode_id); if (node.uri && node.group!='text' && node.group!='undefined' && node.uri!='http://scigraph.springernature.com/pub.10.1007/s00453-020-00717-3') { //console.log(node.uri);$("#side_title").html("<a title='Open in new page' href='/resource?u=" + node.uri + "'>" + node.label + "</a>"); fillInURIpreview(node.uri); setTimeout(function () { if (!bclick){ slider.slideReveal("show"); bclick=false; } }, 500); } } } function actionJumpPage(data) { // https://github.com/almende/vis/issues/743 data.event.preventDefault(); if (data.nodes) { bclick=true; // console.log(data.nodes); var thisnode_id = data.nodes[0]; // assuming one node is clicked at a time! var node = nodes.get(thisnode_id); if(node.uri && node.group!='text' && node.group!='undefined' && node.uri!='http://scigraph.springernature.com/pub.10.1007/s00453-020-00717-3'){ // console.log(node); url = "/resource?u=" + node.uri; window.location.href=url; } } } function fillInURIpreview(uri_hash_safe) { $("#slide_contents").empty();$("#slide_contents").html("<i>loading..</i>"); $.get( "/explorer/ajax_resource?u=" + uri_hash_safe, // {u : uri_hash_safe}, // => causes unwanted char encodings! function(data) {$("#slide_contents").html(data); } ); } // create an array with nodes var nodeData=[ { id: "sg:pub.10.1007/3\u002D540\u002D60220\u002D8_84", label: "sg:pub.10.1007/3\u002D540\u002D60220\u002D8_84", uri : "http://scigraph.springernature.com/pub.10.1007/3-540-60220-8_84", group: "article" }, { id: "schema:ScholarlyArticle", label: "schema:ScholarlyArticle", uri : "http://schema.org/ScholarlyArticle", group: "text" }, { id: "rdf:type", label: "rdf:type", uri : "http://www.w3.org/1999/02/22-rdf-syntax-ns*hash*type", group: "predicate_uri", color:{border:'#4ae54a'}, }, { id: "sg:pub.10.1007/s00453\u002D020\u002D00717\u002D3", label: "Improved Approximation Algorithms for Path Vertex Covers ...", uri : "http://scigraph.springernature.com/pub.10.1007/s00453-020-00717-3", icon: { size: 110, color: 'grey'}, group: "article" }, { id: "sg:journal.1047644", label: "Algorithmica", uri : "http://scigraph.springernature.com/journal.1047644", group: "journal" }, { id: "schema:isPartOf", label: "schema:isPartOf", uri : "http://schema.org/isPartOf", group: "predicate_uri", color:{border:'#9E9E9E'}, }, { id: "https://app.dimensions.ai/details/publication/pub.1127760134", label: "https://app.dimensions.ai/details/publication/pub.1127760134", uri : "https://app.dimensions.ai/details/publication/pub.1127760134", group: "text" }, { id: "schema:sameAs", label: "schema:sameAs", uri : "http://schema.org/sameAs", group: "predicate_uri", color:{border:'#9E9E9E'}, }, { id: "schema:about", label: "schema:about", uri : "http://schema.org/about", group: "predicate_uri", color:{border:'#9E9E9E'}, }, { id: "sg:pub.10.1007/s13119\u002D011\u002D0002\u002D7", label: "sg:pub.10.1007/s13119\u002D011\u002D0002\u002D7", uri : "http://scigraph.springernature.com/pub.10.1007/s13119-011-0002-7", group: "article" }, { id: "anzsrc\u002Dfor:1117", label: "Public Health and Health Services", uri : "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1117", group: "concept" }, { id: "sg:pub.10.1007/978\u002D3\u002D319\u002D21741\u002D3_6", label: "sg:pub.10.1007/978\u002D3\u002D319\u002D21741\u002D3_6", uri : "http://scigraph.springernature.com/pub.10.1007/978-3-319-21741-3_6", group: "article" }, { id: "anzsrc\u002Dfor:11", label: "Medical and Health Sciences", uri : "http://purl.org/au-research/vocabulary/anzsrc-for/2008/11", group: "concept" }, { id: "schema:citation", label: "schema:citation", uri : "http://schema.org/citation", group: "predicate_uri", color:{border:'#9E9E9E'}, }, { id: "https://doi.org/10.1007/s00453\u002D020\u002D00717\u002D3", label: "https://doi.org/10.1007/s00453\u002D020\u002D00717\u002D3", uri : "https://doi.org/10.1007/s00453-020-00717-3", group: "text" }, ] // console.log(nodeData) // create an array with edges var edgeData=[ { from: "sg:pub.10.1007/s00453\u002D020\u002D00717\u002D3", to: "schema:about" }, { from: "schema:about", to: "anzsrc\u002Dfor:11" }, { from: "sg:pub.10.1007/s00453\u002D020\u002D00717\u002D3", to: "schema:about" }, { from: "schema:about", to: "anzsrc\u002Dfor:1117" }, { from: "sg:pub.10.1007/s00453\u002D020\u002D00717\u002D3", to: "schema:citation" }, { from: "schema:citation", to: "sg:pub.10.1007/3\u002D540\u002D60220\u002D8_84" }, { from: "sg:pub.10.1007/s00453\u002D020\u002D00717\u002D3", to: "schema:citation" }, { from: "schema:citation", to: "sg:pub.10.1007/978\u002D3\u002D319\u002D21741\u002D3_6" }, { from: "sg:pub.10.1007/s00453\u002D020\u002D00717\u002D3", to: "schema:citation" }, { from: "schema:citation", to: "sg:pub.10.1007/s13119\u002D011\u002D0002\u002D7" }, { from: "sg:pub.10.1007/s00453\u002D020\u002D00717\u002D3", to: "schema:isPartOf" }, { from: "schema:isPartOf", to: "sg:journal.1047644" }, { from: "sg:pub.10.1007/s00453\u002D020\u002D00717\u002D3", to: "schema:sameAs" }, { from: "schema:sameAs", to: "https://app.dimensions.ai/details/publication/pub.1127760134" }, { from: "sg:pub.10.1007/s00453\u002D020\u002D00717\u002D3", to: "schema:sameAs" }, { from: "schema:sameAs", to: "https://doi.org/10.1007/s00453\u002D020\u002D00717\u002D3" }, { from: "sg:pub.10.1007/s00453\u002D020\u002D00717\u002D3", to: "rdf:type" }, { from: "rdf:type", to: "schema:ScholarlyArticle" }, ] // console.log(edgeData) var nodes = new vis.DataSet(nodeData); var edges = new vis.DataSet(edgeData); var options = { autoResize: true, clickToUse: false, physics:{ barnesHut:{gravitationalConstant:-30000}, stabilization: {iterations:2500} }, interaction:{ hover: true, navigationButtons: true, zoomView: false }, nodes: { shape: 'dot', size: 30, font: { size: 15, color: 'black' }, borderWidth: 2, }, edges: { color: 'gray', smooth: false, length : 150, arrows: { to: {enabled: true, scaleFactor:0.2, type:'arrow'}, middle: {enabled: false, scaleFactor:1, type:'arrow'}, from: {enabled: false, scaleFactor:1, type:'arrow'} }, }, groups: { primary_uri: { color: { border:'#325D94', background: 'lightyellow', highlight: { border:'#325D94', background: '#FFF59D' }, hover: { border:'#325D94', background: '#FFF59D' }, }, size: 60, font: { size: 18, color: 'black' }, }, predicate_uri: { shape: 'box', color: { background: 'white', border: 'lightgreen', // overridden above highlight: { background: 'white', border: 'red' }, hover: { background: 'white', border: '#F44336' }, }, }, ontology: { // not used shape: 'icon', icon: { face: 'FontAwesome', code: '\uf1db', size: 50, color: 'grey' } }, organization: { shape: 'icon', icon: { face: 'FontAwesome', code: '\uf1ad', size: 50, color: '#667eb0' } }, person: { shape: 'icon', icon: { face: 'FontAwesome', code: '\uf007', size: 80, color: '#57169a' } }, concept: { shape: 'icon', icon: { face: 'FontAwesome', code: '\uf0eb', size: 50, color: '#19b3ee' } }, concept_scheme: { shape: 'icon', icon: { face: 'FontAwesome', code: '\uf187', size: 80, color: '#2589b0' } }, article: { shape: 'icon', icon: { face: 'FontAwesome', code: '\uf1ea', size: 80, color: '#2589b0' } }, journal: { shape: 'icon', icon: { face: 'FontAwesome', code: '\uf115', size: 80, color: '#2589b0' } }, book: { shape: 'icon', icon: { face: 'FontAwesome', code: '\uf02d', size: 60, color: '#2589b0' } }, grant: { shape: 'icon', icon: { face: 'FontAwesome', code: '\uf0c3', size: 40, color: 'darkblue' } }, conference: { shape: 'icon', icon: { face: 'FontAwesome', code: '\uf19d', size: 60, color: '#94190c' } }, metrics: { shape: 'icon', icon: { face: 'FontAwesome', code: '\uf080', size: 40, color: '#b09390' } }, text: { shape: 'text', font: { color: '#343434', }, } } } // NORMALLY this is how you render the viz (done via tabs click) //render_viz('mynetwork', nodeData, edgeData); // EXAMPLE for reusing code for another viz: // \$('#modal_network').on('show.bs.modal', function (event) { // render_viz('network_inside_modal'); // })