Improved approximation algorithms for path vertex covers in regular graphs

DOI10.1007/S00453-020-00717-3zbMATH Open1455.68152arXiv1811.01162OpenAlexW3028203334MaRDI QIDQ2006949FDOQ2006949

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

Publication date: 12 October 2020

Published in: Algorithmica (Search for Journal in Brave)

Abstract: Given a simple graph $G=(V,E)$ and a constant integer $kge2$, the $k$-path vertex cover problem ({sc P$k$VC}) asks for a minimum subset $FsubseteqV$ of vertices such that the induced subgraph $G[V-F]$ does not contain any path of order $k$. When $k=2$, this turns out to be the classic vertex cover ({sc VC}) problem, which admits a $left(2-mThetaleft(frac1log|V|ight)ight)$-approximation. The general {sc P$k$VC} admits a trivial $k$-approximation; when $k=3$ and $k=4$, the best known approximation results for {sc P$3$VC} and {sc P$4$VC} are a $2$-approximation and a $3$-approximation, respectively. On $d$-regular graphs, the approximation ratios can be reduced to $minleft2-frac5d+3+epsilon,2-frac(2-o(1))loglogdlogdight$ for {sc VC} ({it i.e.}, {sc P$2$VC}), $2-frac1d+frac4d-23d|V|$ for {sc P$3$VC}, $fraclfloord/2floor(2d-2)(lfloord/2floor+1)(d-2)$ for {sc P$4$VC}, and $frac2d-k+2d-k+2$ for {sc P$k$VC} when $1lek-2<dle2(k-2)$. By utilizing an existing algorithm for graph defective coloring, we first present a $fraclfloord/2floor(2d-k+2)(lfloord/2floor+1)(d-k+2)$-approximation for {sc P$k$VC} on $d$-regular graphs when $1lek-2<d$. This beats all the best known approximation results for {sc P$k$VC} on $d$-regular graphs for $kge3$, except for {sc P$4$VC} 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$-approximation and a $1.852$-approximation for {sc P$4$VC} on cubic graphs and $4$-regular graphs, respectively. We also present a better approximation algorithm for {sc P$4$VC} on $d$-regular bipartite graphs.

Full work available at URL: https://arxiv.org/abs/1811.01162

zbMATH Keywords

approximation algorithmmaximum independent setregular graphpath vertex coverdefective coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some APX-completeness results for cubic graphs
• On a conjecture of Fink and Jacobson concerning k-domination and k- dependence
• On the \(k\)-path vertex cover of some graph products
• Minimum \(k\)-path vertex cover
• The vertex cover \(P_3\) problem in cubic graphs
• On the vertex \(k\)-path cover
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• On the weighted \(k\)-path vertex cover problem
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• A better approximation ratio for the vertex cover problem
• On the power of unique 2-prover 1-round games
• Node-Deletion Problems on Bipartite Graphs
• On approximation properties of the Independent set problem for degree 3 graphs
• The \(k\)-path vertex cover of rooted product graphs
• The complexity of dissociation set problems in graphs
• Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
• Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
• The k-Observer Problem on d-regular Graphs

Cited In (2)

• Computing connected-\(k\)-subgraph cover with connectivity requirement
• Analyzing the 3-path vertex cover problem in planar bipartite graphs

This page was built for publication: Improved approximation algorithms for path vertex covers in regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2006949)