Improved Approximation Algorithms for Path Vertex Covers in Regular Graphs
- PDF / 3,537,789 Bytes
- 24 Pages / 439.37 x 666.142 pts Page_size
- 93 Downloads / 256 Views
Improved Approximation Algorithms for Path Vertex Covers in Regular Graphs An Zhang1 · Yong Chen1 · Zhi‑Zhong Chen2 · Guohui Lin3 Received: 23 June 2019 / Accepted: 21 April 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Given a simple graph G = (V, E) and a constant integer k ≥ 2 , the k-path vertex cover problem (PkVC) asks for a minimum subset F ⊆ V 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 (VC) problem, which admits a 2 − Θ log1|V| -approximation. The general PkVC admits a trivial k-approximation; when k = 3 and k = 4 , 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 min 2 −
2−
1 d
+
4d−2 3d|V|
for P3VC,
5 d+3 ⌊d∕2⌋(2d−2) (⌊d∕2⌋+1)(d−2)
(2−o(1)) log log d for VC log d P4VC, and 2d−k+2 for d−k+2
+ 𝜖, 2 − for
(i.e., P2VC),
PkVC when
1 ≤ k − 2 < d ≤ 2(k − 2) . By utilizing an existing algorithm for graph defective col⌊d∕2⌋(2d−k+2) oring, we first present a (⌊d∕2⌋+1)(d−k+2)-approximation for PkVC on d-regular graphs when 1 ≤ k − 2 < d . This beats all the best known approximation results for PkVC on d-regular graphs for k ≥ 3 , 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 + 𝜖)-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. Keywords Path vertex cover · Regular graph · Defective coloring · Maximum independent set · Approximation algorithm
* Guohui Lin [email protected] Extended author information available on the last page of the article
13
Vol.:(0123456789)
Algorithmica
1 Introduction We investigate a vertex deletion problem called the minimum k-path vertex cover problem, denoted as PkVC, which is a generalization of the classic minimum vertex cover (VC) problem [13]. The PkVC problem has received a number of studies in the literature, and it has applications in wireless sensor networks such as constructing optimal connectivity paths and in networking security such as monitoring the message traffic and detecting malicious attacks [1]. Given a simple graph G = (V, E) and a constant integer k ≥ 2 , a k-path (or, a path of order k) is a simple path containing k vertices; the PkVC problem asks for a minimum subset F ⊆ V of vertices such that the induced subgraph G[V − F] (set minus operation) does not contain any k-path [7, 15, 16]. When k = 2 , this turns out to be VC. In the literature, a k-path vertex cover is also called a vertex k-path cover [6], or a vertex cover Pk [25, 26], or a Pk vertex cover [10], or a k-observer [1, 24]. Also, when F ⊆ V is a (2-path) vertex cover, V − F is known as an independent set, and when F ⊆ V is a 3-path vertex cover, V − F is known as a dissociation set. The maximum in
Data Loading...
