Layering and reverse extension for weighted $k$-path vertex cover

Acknowledgement

This work is supported by the NNSF of China (Grants 12371316, 92567201), the PNSF of Zhejiang China (Grant LZ25A010001), and the NSERC Canada.

Introduction

Throughout the paper, we consider a vertex non-negatively weighted simple graph $G=(V,E)$. In the special case where the vertices have the uniform weight, the graph is also called unweighted. Unless otherwise explicitly specified, the graphs and the problems are vertex-weighted.

For an integer $k \ge2$, a $k$-path in the graph $G$ is a simple path on $k$ vertices. A vertex subset $C \subseteq V$ is a $k$-path vertex cover, denoted as $k$PVC, if every $k$-path in $G$ contains at least a vertex of $C$, or equivalently, the subgraph of $G$ obtained by removing the vertices of $C$ and those edges incident at the vertices of $C$, i.e., $G[V \setminus C]$, does not contain any $k$-path. In the latter sense, $C$ is also called a deletion set for convenience. One sees that when $k=2$, a 2-path is an edge, and a 2PVC is a classic vertex cover.

The weighted $k$PVC problem is to find a $k$PVC $C$ to minimize the total weight of the vertices in $C$, i.e., $w(C)=\sum_{v\in C}w(v)$, where $w(\cdot)$ is the given nonnegative vertex weight function for the input graph. The problem on unweighted graphs was first introduced by Brešar et al. [8], and later the weighted version was first studied by Brešar et al. [10], which generalize the classic vertex cover problem and its weighted variant, respectively. In this paper, we study the weighted $k$PVC problem for any fixed integer $k \ge3$, from the perspective of approximation algorithms.

Previous work

The classic vertex cover, or 2PVC, problem and its weighted variant are NP-hard [14] and APX-hard [1], even on cubic graphs. They admit a 2-approximation algorithm [4] but, assuming the Unique Games Conjecture (UGC), are not approximable within $2-\epsilon$ for any positive $\epsilon$ [17]. In the pioneering work of Brešar et al. [8], unweighted $k$PVC is shown NP-hard, and consequently the weighted variant is NP-hard too, for every $k \ge3$.

On the approximability, given a vertex-weighted graph $G=(V,E)$, one can construct an instance of the weighted set cover problem in which every $k$-path of $G$ becomes an “element” and every vertex of $V$ becomes a set that “covers” all the $k$-paths passing it and has a weight. In particular, one observes that in such an instance, every element occurs in exactly $k$ sets (typically the number of sets is called frequency). Therefore, Bar-Yehuda and Even’s [4] and Hochbaum’s [16] algorithms for the low-frequency weighted set cover problem can be employed, to become the first $k$-approximation algorithm for the weighted $k$PVC problem. Since its first formal study [10] in 2014, the only improvement was made in 2021 by Brüstle et al. [11], who presented a $(k-\frac{1}{2})$-approximation algorithm.

For the unweighted $k$PVC problem, Lee presents an $O(\log k)$-approximation algorithm [18].

On the inapproximability side, Brešar et al. showed that an $\alpha$-approximation algorithm for the unweighted $k$PVC problem yields an $\alpha$-approximation algorithm for the classic vertex cover problem [8]. Therefore, assuming the UGC, the unweighted, and consequently the weighted, $k$PVC problem is not approximable within $2-\epsilon$ for any positive $\epsilon$.

Besides the above general results, there are also studies on some specific low values of $k$ and on some restricted graph classes. For instance, Tu and Zhou gave two 2-approximation algorithms for weighted 3PVC, based on the primal-dual method and the layering method [25, 24], respectively. For weighted 4PVC, Camby et al. gave a 3-approximation algorithm [12]. These are the state-of-the-art results for $k=3$ and 4, respectively.

When the graphs are unweighted and regular, better constant approximation ratios are known for $k \ge3$ [20, 26]. For unweighted 3PVC, a polynomial-time approximation scheme (PTAS) is known for planar graphs [23], and a PTAS is known for bounded-heterogeneity ball graphs [27].

Exact polynomial-time algorithms are also known for several restricted graph classes. Brešar et al. [8] showed that unweighted $k$PVC is solvable in linear time for trees; Tu [21] gave an exact polynomial-time algorithm for cactus graphs. For weighted $k$PVC, Brešar et al. [10] gave exact polynomial-time algorithms for complete graphs, paths, cycles, and trees; in particular, their algorithm for trees runs in $O(k|V|)$ time. When $k=3$, since unweighted 3PVC is dual to the maximum dissociation set problem, the results of Orlovich et al. [19] imply the polynomial-time solvability of unweighted 3PVC on chordal graphs, weakly chordal graphs, interval-filament graphs, and AT-free graphs. Brešar et al. [9] also gave a linear-time algorithm for unweighted 3PVC on 4-path-tidy graphs¹ Further exact, approximation, and parameterized algorithmic results have been summarized in a survey [22].

Our contribution

We study the weighted $k$PVC problem for any fixed integer $k \ge3$, from the approximation algorithm perspective. We adopt the Layering and Reverse Extension local ratio framework of Bar-Yehuda et al. [3], and carefully design local cost functions, leading to an approximation algorithm of ratio $\frac{3k-1}{4}$ for odd $k \ge3$ and of ratio $\frac{3k}{4}$ for even $k \ge4$. When $k=3$ and $k=4$, these ratios are 2 and 3, respectively, matching the state-of-the-art approximation ratios for the corresponding special cases.

The algorithm framework

The Layering and Reverse Extension framework has a forward phase of recursive layering and a backward phase of solution extension, with its performance analyzed by the local ratio technique [3]. During the forward layering phase, we abuse $G=(V,E)$ to denote the current remaining graph in which every vertex of $V$ has a positive remaining weight. In the current iteration, a vertex subset $U \subseteq V$ is located such that the induced subgraph on $U$, $G[U]$, contains a spanning subgraph isomorphic to a carefully designed structure $H$, which in our case is a maximal-arm spider (in Definition 2). Then, with respect to a local cost function designed for the vertices of $U$, a scaling factor is found and the vertices of $U$ of the scaled weights form a layer, which is subtracted from the graph $G$ to give rise to at least one zero-weighted vertex. The zero-weighted vertices are then removed, and layering continues into the next iteration.

When an iteration is reached in which the remaining graph $G$ can be solved exactly, which in our case is spider-free, a minimal solution is obtained and the second reverse extension phase starts to restore the removed vertices in the reverse order of layering iterations, and at the end returns a $k$PVC for the original graph.

For the performance analysis, the designed local cost function for layering is used to bound the weight of the achieved solution in each layer with respect to the optimum local to that layer, following the good-local-cost formulation of Aprile et al. [2].

The main result and paper organization

We introduce some key notations and the spider structures in § 3. § 4 presents a polynomial-time dynamic programming exact algorithm for spider-free graphs, that is, the input graph does not contain the defined spider structure as a subgraph. The main algorithm of Layering and Reverse Extension, together with the local-ratio analysis and the running time analysis, are in § 5. § 6 concludes the paper.

Preliminaries

All graphs are finite, simple, and undirected. Given a graph $G$ and its nonnegative vertex weight function $w: V(G) \to\mathbb{Q}_{\ge0}$ and $C \subseteq V(G)$, let $w(C)=\sum_{v\in C} w(v)$ for any vertex subset $C$, and let

We remark that a maximal-arm spider is greedily grown from a three-arm spider, and thus it is not necessarily unique, neither necessarily has a unique number of arms, but all depending on what the new arms are and how they are discovered.

In our Layering and Reverse Extension algorithm for the weighted $k$PVC problem, we will use maximal-arm spiders to construct layers. The next two lemmas give the first idea on why they are important to the approximation ratio we want to prove.

Proof. Suppose $P$ is a $k$-path in $G$ passing the center $c$. We claim that $P$ contains at least an arm-vertex of $A$, since otherwise from $P$ one can find a new arm for $A$, contradicting the maximality. In other words, $C \setminus\{c\}$ is still a $k$PVC. This proves the lemma.

Basically, using Lemma 1, we assign a weight of 1 to every arm-vertex while a weight of $p-1$ to the center. This way, the minimum cost of covering a $p$-arm spider is at least $p-1$. Furthermore, given that all these weights are positive, by Lemma 2 our to-be computed solution will not contain all the vertices of the spider but at most $pm-1+(p-1)=\frac{k+1}{2}-2$ when $k$ is odd (or a similar value when $k$ is even). It follows that the approximation ratio is no more than $\frac{3k-1}{4}$. We will formally present the algorithm and prove its performance in the next two sections.

Lemma 2 also inspires the definition of minimal $k$PVC: A $k$PVC $C$ of $G$ is minimal if for every $v \in C$, $C \setminus\{v\}$ is no longer a $k$PVC.

Proof. Consider a vertex $v \in C$. Since $C \setminus\{v\}$ is not a $k$PVC, there exists a $k$-path $P$ that is not covered by $C \setminus\{v\}$, i.e., $V(P) \cap(C \setminus\{v\}) = \varnothing$. On the other hand, since $C$ is a $k$PVC, $P$ must contain at least one vertex of $C$, and thus exactly the vertex $v$.

Conversely, removing $v$ from $C$ will leave $P$ uncovered, and thus $C$ is minimal.

A polynomial-time exact algorithm for spider-free graphs

In this section, we show that the $k$PVC problem on spider-free graphs is solvable in polynomial time. A spider-free graph is one that does not contain any three-arm spider $T_k$ defined in Eq. (1), and thus it is the boundary case terminating the first layering phase of the algorithm. For distinction, we fix a spider-free graph $H=(V,E)$ for discussion.

There are two steps in the exact algorithm. First, we show that the spider-free graph $H$ has pathwidth bounded by a function depending only on $k$, and construct a path decomposition of bounded width for $H$. We then give a dynamic program on this path decomposition to compute a minimum weight $k$PVC for $H$.

Bounded pathwidth and a path decomposition

Given a graph, an edge contraction merges the two connecting vertices into one and removes the loop just formed. A graph $F$ is a minor of $H$ if $F$ can be obtained from $H$ by a sequence of edge contractions, edge and vertex deletions. An edge subdivision adds new vertices to the edge whereby breaking the edge into two. A graph $F$ is a topological minor of $H$ if a subdivision of $F$ is (isomorphic to) a subgraph of $H$. One sees that a topological minor is a minor, but the converse is not necessarily true. Nevertheless, when the minor is a subcubic graph, it is a topological minor too due to Diestel [13].

Since every subdivision of the three-arm spider $T_k$ contains $T_k$ as a subgraph, this proposition immediately implies that excluding $T_k$ as a subgraph in $H$ also excludes $T_k$ as a minor. We summarize this conclusion in the next lemma.

Given a graph $H$, a tree decomposition represents the vertices of $H$ as subtrees of a tree $T$, in such a way that vertices in $H$ are adjacent only when the corresponding subtrees of $T$ overlap. In detail, a tree decomposition [13 Section 12.3] is a pair $(\mathcal{B}, T)$, where $\mathcal{B} = \{B_1, B_2, \ldots, B_q\}$ is a family of subsets (called bags) of vertices of $H$, and $T$ is a tree whose nodes are these bags, satisfying the following properties: 1) every vertex of $H$ appears in (called associated with) some bags that are connected in $T$, and 2) for every edge $(u, v)$ in $H$, both $u$ and $v$ appear in some bags. The width of the tree decomposition is the size of its largest bag minus one, i.e., $\max_{1 \le i \le q} |B_i| - 1$, and the treewidth $\operatorname{tw}(H)$ of the graph $H$ is the minimum width among all possible tree decompositions of $H$.

A tree decomposition in which the underlying tree $T$ is a path graph is called a path decomposition of $H$, and the width parameter derived from this path decomposition is called pathwidth. Analogously, the pathwidth $\operatorname{pw}(H)$ of the graph $H$ is the minimum width among all possible path decompositions of $H$ [13]. We remark that for notational convenience, for a path decomposition $(\mathcal{B}, P)$, where $\mathcal{B} = \{B_1, B_2, \ldots, B_q\}$ and $P$ is the underlying path, we assume these bags are indexed to match their node order on the path $P$. One sees that every graph has path and tree decompositions, for example a single bag of all the vertices of the graph. Efforts are put in finding an optimal path or tree decomposition that achieves the minimum pathwidth or treewidth, correspondingly, followed by their applications.

We next use the following result on the pathwidth of a graph due to Bienstock et al. [5] (where a forest is a graph consisting of one or multiple trees).

Since $T_k$ is a tree, Lemmas 4 and 5 give an explicit constant upper bound on the pathwidth of the spider-free graph $H$.

Proof. One sees that when $k = 2m + 1$, $|V(T_k)| = 1 + 3m = \dfrac{3k-1}{2}$, and thus $\operatorname{pw}(H) \le|V(T_k)| - 2 = \dfrac{3k-5}{2}$. When $k = 2m$, $|V(T_k)| = 1 + (m - 1) + m + m = 3m = \dfrac{3k}{2}$, and thus $\operatorname{pw}(H) \le|V(T_k)| - 2 = \dfrac{3k-4}{2}$. □

For a fixed $k$, a bounded-width path decomposition of a spider-free graph $H$ can be constructed in linear time. For example, one can first call Bodlaender’s algorithm [6] to construct a tree decomposition of width at most $p_k$ for $H$ in linear time, and then call Bodlaender and Kloks’s algorithm [7] to construct a path decomposition of width at most $p_k$ for $H$ in linear time. In the sequel, we assume a path decomposition of width at most $p_k$ for $H$ is readily available.

The following standard transformation shows that imposing this nice form does not increase the width.

Proof. We construct the bags in the new path decomposition sequentially and explicitly, starting with the empty bag $B'_0 = \varnothing$. Assuming without loss of generality that $B'_i$ has just been constructed using a sub-collection of bags $\{B_1, B_2, \ldots, B_{j-1}\}$ of $\mathcal{B}$, and that $B'_i = B_{j-1}$, where $B_0 = \varnothing$ for notational convenience. Forgetting one vertex of $B'_i \setminus B_j = B_{j-1} \setminus B_j$ at a time to produce $s = |B_{j-1} \setminus B_j|$ new bags sequentially, namely, $B'_{i+1}, \ldots, B'_{i+s}$ such that $B'_{i+s} = B_{j-1} \cap B_j$. Next, introducing one vertex of $B_j \setminus B_{j-1}$ at a time to produce $t = |B_j \setminus B_{j-1}|$ new bags sequentially, namely, $B'_{i+s+1}, \ldots, B'_{i+s+t}$. One thus sees that $B'_{i+s+t} = B_j$. This way, using the bag $B_j$, we have constructed $s + t = |B_{j-1} \setminus B_j| + |B_j \setminus B_{j-1}|$ sequential bags such that these $i + s + t$ bags satisfy the second property in Definition 3. At the end of using the last bag $B_q$, we achieve a sequence of bags $B'_0,B'_1,\ldots,B'_{\ell}$ such that $B'_{\ell}=B_q$. Lastly, forget the vertices of $B_r$ one at a time from $B'_{\ell}$ to produce $|B_q|$ bags with the last one $B'_{q'}=\emptyset$, where $q'=\ell+|B_q|$. Therefore, both properties in Definition 3 are satisfied.

For notational convenience, we denote $B_{q+1}=\emptyset$. We have $q'=\sum_{j=1}^{q}|B_j\setminus B_{j-1}|+\sum_{j=2}^{q+1}|B_{j-1}\setminus B_j|=|V(H)|+|V(H)|=2|V(H)|$, i.e., every vertex of $H$ is introduced exactly once and forgotten exactly once. This proves the number of constructed bags in $\mathcal{B}'$.

It is seen that all the old bags of $\mathcal{B}$ occur in $\mathcal{B}'$, and thus every edge of $H$ continues to exist. Also, by the ways of forgetting and introducing vertices from $B_{j-1}$ to achieve $B_{j-1}\cap B_j$ and then to achieve $B_j$, every vertex of $H$ continues to associate with an interval of bags in $\mathcal{B}'$, and thus a subpath of the path $P'$. That is, $\mathcal{B}'$ is a nice path decomposition for $H$. Since we do not produce any bag of size larger than $\max_{1\leq j\leq q}|B_j|$, the pathwidth of $\mathcal{B}'$ is the same as that of $\mathcal{B}$. One clearly sees that the construction takes $O(n+q)$ time, which is linear. This finishes the proof of the lemma. □

By Lemma 6, in the sequel, we assume a nice path decomposition $\mathcal{B}=\{B_0,B_1,\ldots,B_{2n}\}$ of width at most $p_k$ for a spider-free graph $H$ is readily available, where $n=|V(H)|$ and each vertex of $H$ is introduced first and then forgotten from a later bag. We use $\mathcal{B}$ to solve the weighted $k$PVC problem on $H$ exactly.

A dynamic programming exact algorithm

Consider a spider-free graph $H$ and a nice path decomposition $\mathcal{B}=\{B_0,B_1,\ldots,B_{2n}\}$ of width at most $p_k$ for $H$ stated right in the above. Our algorithm examines these bags one by one sequentially, and distinguishes on how the current bag $B_i$ is obtained from $B_{i-1}$, by introducing or forgetting a vertex $v$.

Denote $U_i=\bigcup_{j=1}^{i}B_j$, the set of vertices introduced up to $B_i$, and the induced subgraph $H_i=H[U_i]$. Importantly, since when a vertex is forgotten all its neighbors must have all been introduced, there is no edge between the set $U_i\setminus B_i$ of vertices (which have been forgotten) and the set $V(H)\setminus U_{i-1}$ of vertices (which are to be introduced). This leads to our idea to maintain the collection of all partial $k$-paths in the current graph $H[U_i\setminus C]$, where $C\subseteq U_i$ is the set of deleted vertices, and update them when the vertex $v$ is introduced, deleted, or forgotten. We point out that the existence of a complete $k$-path indicates the infeasibility of the deleted vertex set $C$.

Furthermore, we ignore the detailed vertices of $C\cap(U_i\setminus B_i)$, but only record their total weight. On the other hand, we do keep the detailed vertices of $D=C\cap B_i$. With respect to $D$, a partial $k$-path is denoted as a vector

where a vertex $v\in B_i\setminus D$ denotes a retained vertex, $0$ denotes an unused position, and each occurrence of $\star$ denotes a distinct retained forgotten vertex of $(U_i\setminus B_i)\setminus C$. The consecutive occupied positions correspond to adjacent distinct vertices. Let $\Phi$ denote the collection of all such partial $k$-paths that are valid in the current residual graph; define a dynamic programming (DP) state as a pair $(D,\Phi)$, and $\mathrm{DP}_i[D,\Phi]$ stores the minimum weight of a deletion set in $U_i$ producing this state. That is, if several deletion sets produce the same state, then only the minimum-weight one is kept for backtracking purpose.

At the initial empty bag $B_0=\emptyset$, we initialize $\Phi=\{(0,\ldots,0)\}$ and set $\mathrm{DP}_0[\emptyset,\Phi]=0$. Below we assume all possible states $(D,\Phi)$ at the bag $B_{i-1}$ have been decided, and their associated minimum weight $\mathrm{DP}_{i-1}[D,\Phi]$ computed. We distinguish the two introduce and forget transitions.

Case 1: $B_i=B_{i-1}\cup\{v\}$. For each state $(D,\Phi)$ at $B_{i-1}$, the DP algorithm considers whether $v$ is deleted or retained.

If $v$ is deleted, then $v$ is added to $D$, its weight $w(v)$ is added to the objective value, and all the partial $k$-paths remain unchanged. That is, a valid state $(D\cup\{v\},\Phi)$ is reached and $\mathrm{DP}_i[D\cup\{v\},\Phi]=\mathrm{DP}_{i-1}[D,\Phi]+w(v)$.

Suppose that $v$ is retained. Firstly, each partial $k$-path $\sigma=(\sigma_1,\ldots,\sigma_k)\in\Phi$ remains valid, since $v$ does not have to be used in the path. In addition, $v$ can be added the path $\sigma$ to produce new representations, by replacing each position $x$ with $\sigma_x=0$ by $v$. To be valid, every occupied position adjacent to $x$, i.e., $\sigma_{x-1}$ and $\sigma_{x+1}$ if they are within range, has to have a vertex of $B_{i-1} \subset B_i$ adjacent to $v$ in the underlying graph $H$, or otherwise the new representation is invalid and deleted. We note that an occupied neighboring position cannot be $\star$, which represents a forgotten vertex not adjacent to $v$ in the graph $H$. The final collection, denoted as $\Phi'$, is the union of $\Phi$ and these new valid partial $k$-paths containing $v$. We have $\mathrm{DP}_i[D,\Phi'] = \mathrm{DP}_{i-1}[D,\Phi]$.

Case 2: $B_i = B_{i-1} \setminus\{v\}$. For each state $(D,\Phi)$ at $B_{i-1}$, the DP algorithm considers whether $v$ has been deleted or is retained.

If $v \in D$, i.e., $v$ has been deleted, then it is removed from $D$ to update $D$ to be a subset of $B_i$, and all the partial $k$-paths remain unchanged. That is, a valid state $(D \setminus\{v\},\Phi)$ is reached and $\mathrm{DP}_i[D \setminus\{v\},\Phi] = \mathrm{DP}_{i-1}[D,\Phi]$.

Suppose that $v \notin D$, i.e., $v$ is retained. For each partial $k$-path $\sigma= (\sigma_1,\ldots,\sigma_k) \in\Phi$, if it does not contain $v$, then it remains valid; otherwise, the occurrence of $v$ is replaced by $\star$ while all other symbols remain unchanged. We note that such a symbol-replacement process might lead to identical partial $k$-paths, and if so then only one is kept. For the final collection, denoted as $\Phi'$, we have $\mathrm{DP}_i[D,\Phi'] = \mathrm{DP}_{i-1}[D,\Phi]$.

We also note that in the above two transitions, multiple states at $B_{i-1}$ can lead to the same state at $B_i$, and if so then the algorithm keeps the minimum weight and the associated deletion set for backtracking purpose. At the final empty bag $B_{2n}$, every remaining state corresponds exactly to a $k$PVC of the underlying graph $H$, and the one achieving the minimum weight can be backtracked to produce the deletion set returned as the solution, denoted as $\operatorname{ALG}(H,w)$.

Algorithmic framework of layering and reverse extension

Given a subgraph $H$ of the current vertex positively weighted graph $G = (V,E)$, a non-zero nonnegative function $c_H : V(H) \to\mathbb{Q}_{\geq0}$ that defines the vertex weights in $H$ is called a local cost function for $H$. We use $(H,c_H)$ to denote the vertex non-negatively weighted graph $H$ in which $c_H$ is the vertex weight function.

Layering and reverse extension is an algorithmic framework that, given a weighted graph $G = (V,E)$, cuts off a layer of vertex weights resulting in a smaller graph $G'$, recursively computes a solution for $G'$, then greedily extends the solution using some vertices in the layer to become a solution for the original graph $G$. For an input graph $G = (V,E)$ in which the vertex weight function is $w(\cdot)$, we denote the procedure as $\operatorname{LRE}(G,w)$, in which the detailed steps of computation are depicted in Algorithm 1.

Algorithm 1 $\operatorname{LRE}(G,w)$.

Require: $G = (V,E)$ with vertex weight function $w: V \to\mathbb{Q}_{\geq0}$;

Ensure: a minimal $k$PVC $C$.

1. $Z \leftarrow\{v \in V \mid w(v) = 0\}$;

2. if $(Z \ne\varnothing)$ then

3. $V' \leftarrow V \setminus Z$;

4. $G' \leftarrow G[V']$;

5. $C \leftarrow\operatorname{LRE}(G',w|_{V\setminus Z})$; ▷ recursive call;

6. while $(Z \ne\varnothing)$ do

7. take a vertex $z$ of $Z$; ▷ reverse extension starts;

8. $V' \leftarrow V' \cup\{z\}$;

9. $G' \leftarrow G[V']$;

10. if ($C$ is not a $k$PVC of $G'$) then $C \leftarrow C \cup\{z\}$;

11. $Z \leftarrow Z \setminus\{z\}$;

12. return $C$;

13. if ($G$ is spider-free) then ▷ boundary case;

14. return $\operatorname{ALG}(G,w)$; ▷ a minimum-weight $k$PVC of $G$;

15. else

16. find a maximal-arm spider $H = \{c,Q_1,Q_2,\ldots,Q_p\}$ in $G$; ▷ layering starts;

17. define

18. $\lambda\leftarrow\max\{\mu\geq0 \mid w(v)-\mu\cdot c_H(v) \geq0,\ \forall v \in V(H)\}$;

19. define

20. return $\operatorname{LRE}(G,\bar{w})$; ▷ recursive call;

In Lines 13–20 of the layering phase, the conditional statement distinguishes whether a layering is necessary, namely, if $G$ is spider-free, i.e., boundary case, then (Line 14) the dynamic programming algorithm stated in Theorem 2 is called to solve the instance exactly. Otherwise, (Lines 16–20) a three-arm spider $T_k$ can be located and then greedily a maximal-arm spider $H = \{c,Q_1,Q_2,\ldots,Q_p\}$ containing $T_k$ is formed, where $p \geq3$. The vertices of this spider $H$ form a layer, for which a local cost function $c_H(\cdot)$ is designed (Line 17), and subsequently the coefficient $\lambda$ of the layer is determined so that taking off the layer from the graph $G$ leaves at least one zero-weight vertex. Then the algorithm recursively runs on the graph $G$ with the remaining vertex weights. During the recursive call, in Lines 1–12, the algorithm first removes zero-weighted vertices, then executes Lines 13–20 to find a solution $C$. Upon $C$ is returned, the reverse extension phase starts, in which zero-weighted vertices are scanned in an arbitrary order to restore the graph, so that if $C$ does not remain as a $k$PVC of the current graph, then the scanned vertex is added to $C$. This ensures the final $C$ is a minimal $k$PVC for the original graph $G$.

Proof. The minimality holds trivially if $C$ is a $k$PVC of $G[V' \cup\{z\}]$.

Next suppose $C$ is not a $k$PVC of $G[V' \cup\{z\}]$. One first sees that $C^+ = C \cup\{z\}$ is a $k$PVC of $G[V' \cup\{z\}]$. If $C^+ = C \cup\{z\}$ is not minimal, then there exists an $x \in C$ such that $C \cup\{z\} \setminus\{x\}$ is a $k$PVC of $G[V' \cup\{z\}]$. Since $z$ is not on any $k$-path of $G[V']$, $C \setminus\{x\}$ is a $k$PVC of $G[V']$, contradicting the minimality of $C$ in $G[V']$. This proves that $C^+ = C \cup\{z\}$ is a minimal $k$PVC of $G[V' \cup\{z\}]$. $\square$

Proof. Let $C$ be a $k$PVC of $H$. If the center $c \in C$, then $c_H(C) \ge c_H(c) = p - 1$.

Suppose that $c \notin C$. We conclude from Lemma 1 that $C$ contains at least $p-1$ arm-vertices each of local cost 1. That is, $c_H(C) \ge p - 1$. This proves the lemma. $\square$

Proof. Note that the vertices of $H$ have positive weights of at least 1. By Lemma 2, $C$ does not contain all the vertices of $H$, and thus $c_H(C \cap V(H)) \le c_H(V(H)) - 1$. $\square$

Proof. Let $C$ be a minimal $k$PVC of $G$. By Lemmas 8 and 9, and $p \ge3$, when $k$ is odd,

When $k$ is even,

That is, $(H,c_H)$ is $\rho$-good with the defined $\rho$. $\square$

Proof. Denote $(G_0,w_0) = (G,w)$ the original graph, and $G_i$ denotes the subgraph induced by the vertices having positive residual weight after the $i$-th layering step, and let $w_i$ be the corresponding residual weight function restricted to $V(G_i)$ (that is, for every $v \notin V(G_i)$, $w_i(v) = 0$). The local weighted maximal-arm spider $(H_i,c_{H_i})$ of the $i$-th layer is selected from the graph $G_{i-1}$ with coefficient $\lambda_i$, for $i = 1,2,\ldots,t$, and terminates at the residual spider-free graph $(G_t,w_t)$.

Let $C$ be the $k$PVC returned by LRE, and let $C^*$ be an optimum $k$PVC of $(G,w)$. For every layer $i$, let $\operatorname{OPT}(H_i,c_{H_i})$ denote the minimum-weight of the $k$PVC of $H_i$. Since $C^* \cap V(H_i)$ is a $k$PVC of $H_i$ and $c_{H_i}$ is restricted to $V(H_i)$, we have

Similarly, $C^* \cap V(G_t)$ is a $k$PVC of the spider-free graph $G_t$, and hence

Therefore,

Recall that the returned $C$ is formed by $\operatorname{ALG}(G_t,w_t)$, followed by reverse extension that adds vertices from $V(G_{i-1}) \setminus V(G_i) \subseteq V(H_i)$ into $C$, sequentially for $i=t,t-1,\ldots,1$. For every layer $i$, consider the moment in the reverse-extension process when all vertices of $G_{i-1}$ have been restored. By Lemma 7, the solution at this moment is a minimal $k$PVC of $G_{i-1}$. Moreover, subsequent reverse-extension steps never remove any vertex from the solution. Therefore, the solution at this moment is exactly $C \cap V(G_{i-1})$. That is, $C \cap V(G_{i-1})$ is a minimal $k$PVC of $G_{i-1}$. Since $(H_i,c_{H_i})$ is $\rho$-good in $G_{i-1}$,

Using $w_t(C) = w_t(\operatorname{ALG}(G_t,w_t)) = \operatorname{OPT}(G_t,w_t)$ and $\rho\ge1$, we have

This proves the theorem. □

Proof. A three-arm spider $T_k$ contains at most $3^{k/2}$ vertices interconnected in a specific structure, and thus it can be located, if exists, in $O(n^{3k/2}\cdot\operatorname{poly}(k))$ time. Afterwards, since enumerating all possible arms at the center vertex in the subgraph induced by the vertices outside of the spider takes $O\left(\binom{k}{2}\cdot n^{k/2}\right)$ time, and there are $O(n^{k/2})$ of them, greedily expanding $T_k$ into a maximal-arm spider $H$, in which there are at most $\frac{2n}{k}$ arms, takes $O\left(\frac{k}{2}\cdot n^{k/2}\cdot\frac{2n}{k}\right)=O(n^{k/2+1})$ time.

Given a maximal-arm spider $H$, setting up the local cost function $c_H$, determining the parameter $\lambda$, and updating the vertex weight function $\bar{w}$ takes $O(n+k)$ time. It follows that every layer takes an overall time of $O(n^{3k/2}\cdot\operatorname{poly}(k))$, and it leaves at least a zero-weight vertex in the residual graph. That is, there are at most $n$ layers.

During the reverse extension, when a zero-weight vertex is restored, the feasibility of the current deletion set $C$ can be tested by enumerating all $k$-paths in the restored graph, which takes $O(n^k\cdot\operatorname{poly}(k))$ time. Since there are at most $n$ restorations, the overall reverse extension time is in $O(n^{k+1}\cdot\operatorname{poly}(k))$.

Recall from Theorem 2 that the dynamic programming algorithm produces an exact solution for a spider-free graph, which is a subgraph of $G=(V,E)$, in $O(n\cdot f(k))$ time, where $f(k)$ is a function depending only on $k$. Summing up, a coarse running time bound for the LRE is $O(n^{3k/2+1}\cdot\operatorname{poly}(k)+n\cdot f(k))$, where $\operatorname{poly}(k)$ is a polynomial function in $k$ and $f(k)$ is an exponential function depending only on $k$. We remark that if $k$ is part of the input, then the running time is not necessarily polynomial any more. □

Combining Lemma 10, Theorem 3, and Lemma 11, we have achieved the conclusion stated as Theorem 1, that is, for every fixed integer $k \ge3$, the weighted $k$PVC problem admits a polynomial-time $\rho_k$-approximation algorithm, where

Conclusion

We studied the weighted $k$-Path Vertex Cover problem from the perspective of approximation algorithm, where the input graph is vertex non-negatively weighted. We observed a maximal-arm spider that can be approximated within a factor of $\frac{3k}{4}$, and thus designed it into layers in the Layering and Reverse Extension framework. Furthermore, we proposed a polynomial-time exact dynamic programming algorithm that solves the boundary case of spider-free graphs, based on a path decomposition of bounded width. Using the local-ratio technique, we were able to prove that the performance ratio of our approximation algorithm is no more than $\frac{3k}{4}$. The improvement in the approximation ratio is huge considering the previous best ratio being $k-\frac{1}{2}$, which was improved from an earlier ratio of $k$. Notably, the running time of both the dynamic programming algorithm, and the Layering and Reverse Extension algorithm, is exponential in $k$, and thus requires $k$ to be a fixed constant. It would be interesting to see whether the approximation ratio lower bound is $O(k)$ or not, and if not, how one can improve the ratio into $o(k)$.