Improved approximation algorithms for path vertex covers in regular graphs

DOI10.1007/S00453-020-00717-3MaRDI QIDQ2006949zbMATH OpenOpenAlexFDO

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

Publication date 12 October 2020

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmdefective coloringmaximum independent setpath vertex coverregular graph

Mathematics Subject Classification ID

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) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

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.

Recommendations

• A 2-approximation algorithm for the vertex cover \(P_{4}\) problem in cubic graphs
• Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
• Complexity and algorithms for the connected vertex cover problem in 4-regular graphs
• The connected vertex cover problem in \(k\)-regular graphs
• Approximation algorithms for minimum weight connected 3-path vertex cover

Cites work

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

Cited in

(4)

• Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
• The \(k\)-observer problem on \(d\)-regular graphs
• 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)