Indian Institute of Technology Kharagpur, India and
https://cse.iitkgp.ac.in/~palash/<EMAIL_ADDRESS>https://orcid.org/0000-0003-0071-9464 Indian Institute of Technology
Kharagpur<EMAIL_ADDRESS>https://orcid.org/0009-0009-8805-4583
Indian Institute of Technology Kharagpur, India and
https://cse.iitkgp.ac.in/~skolay/<EMAIL_ADDRESS>https://orcid.org/0000-0002-2975-4856 Indian Institute of Technology
Kharagpur, India<EMAIL_ADDRESS>[100] 2

# Knapsack with Vertex Cover, Set Cover, and Hitting Set

Palash Dey  Ashlesha Hota 111Joint Author Sudeshna Kolay  Sipra Singh 222First
Author

###### Abstract

Given an undirected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, with vertex
weights $(w(u))_{u\in\mathcal{V}}$, vertex values
$(\alpha(u))_{u\in\mathcal{V}}$, a knapsack size $s$, and a target value $d$,
the Vertex Cover Knapsack problem is to determine if there exists a subset
$\mathcal{U}\subseteq\mathcal{V}$ of vertices such that $\mathcal{U}$ forms a
vertex cover, $w(\mathcal{U})=\sum_{u\in\mathcal{U}}w(u)\leqslant s$, and
$\alpha(\mathcal{U})=\sum_{u\in\mathcal{U}}\alpha(u)\geqslant d$. In this
paper, we closely study the Vertex Cover Knapsack problem and its variations,
such as Vertex Cover Knapsack with Budget, Minimal Vertex Cover Knapsack, and
Minimum Vertex Cover Knapsack, for both general graphs and trees. We first
prove that the Vertex Cover Knapsack problem belongs to the complexity class
$\mathsf{NP}$-complete and then study the complexity of the other variations.
We generalize the problem to Set Cover and d-Hitting Set versions and design
polynomial time $H_{g}$-factor approximation algorithm for the Set Cover
Knapsack with target value problem and d-factor approximation algorithm for
d-Hitting Set Knapsack with target value using primal dual method. We further
show that Set Cover Knapsack with budgeted weight and d-Hitting Set Knapsack
with budgeted weight are hard to approximate in polynomial time. Additionally,
we develop a fixed parameter tractable algorithm running in time
$8^{\mathcal{O}(\text{tw})}\cdot n\cdot{\sf min}\\{s,d\\}$ where
$\text{tw},s,d,n$ are respectively treewidth of the graph, the size of the
knapsack, the target value of the knapsack, and the number of items for the
Minimal Vertex Cover Knapsack problem.

###### keywords:

Vertex cover knapsack, Vertex cover knapsack with budget, Minimal vertex cover
knapsack, Minimum vertex cover knapsack, Hitting set, Set cover

###### category:

##  1 Introduction

The Vertex Cover problem is a well-studied classical problem in graph theory
and operations research. Given a graph $\mathcal{G}(\mathcal{V},\mathcal{E})$,
the Vertex Cover problem aims to find a minimum vertex subset
$\mathcal{V}^{\prime}\subseteq\mathcal{V}$ such that for every edge
$(u,v)\in\mathcal{G}[\mathcal{E}]$, either $u$ or $v$ or both exist in
$\mathcal{V}^{\prime}$. In this paper, we explore a novel variation of the
classical Vertex Cover problem in the context of the Knapsack. In the Knapsack
problem, we are given a set of $n$ items, $\mathcal{X}$ = {1, 2, …, n} and a
knapsack of capacity $b$. Each item $i\in[n]$ is associated with size
$\theta_{i}$ and values $p_{i}$. The computational question is to find a
subset $\mathcal{I}\subseteq\mathcal{X}$ to be put into the knapsack of
capacity $b$ that maximizes the value of the knapsack without exceeding its
capacity constraint. This paper delves into the problem Vertex Cover Knapsack,
where given an undirected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, with
vertex weights $(w(u)){u\in\mathcal{V}}$, vertex values
$(\alpha(u)){u\in\mathcal{V}}$, a knapsack size $s$, and a target value $d$,
the Vertex Cover Knapsack problem is to determine if there exists a subset
$\mathcal{U}\subseteq\mathcal{V}$ of vertices such that $\mathcal{U}$ forms a
vertex cover, $w(\mathcal{U})=\sum_{u\in\mathcal{U}}w(u)\leqslant s$, and
$\alpha(\mathcal{U})=\sum_{u\in\mathcal{U}}\alpha(u)\geqslant d$. We study
several interesting variations of this problem like Vertex Cover Knapsack with
Budget, Minimal Vertex Cover Knapsack, and Minimum Vertex Cover Knapsack.
These problems are formally defined in Section 2. Vertex Cover is a special
case of Set Cover and 2-HITTING SET. We design polynomial time approximation
algorithms for Set Cover Knapsack with target value problem and show similar
results for d-Hitting Set and Vertex Cover Knapsack. We also show that Vertex
Cover Knapsack with budgeted weight does not admit a polynomial time
approximation algorithm unless $P=\mathsf{NP}$.

These problems often find applications in various domains, including wireless
network design, especially in the context of leasing mobile towers. Consider a
scenario where a company aims to establish mobile towers in different areas to
efficiently serve its customers while minimizing leasing costs within a budget
constraint. Additionally, the company must ensure that it meets the target or
subscribed customer base. This situation can be depicted through an undirected
weighted graph $\mathcal{G}$, where vertices symbolize towers and edges
represent the connectivity range. Each tower vertex is associated with a
value, indicating the number of customers it can serve, and a weight,
representing the leasing cost. Moreover, there exists a budget constraint,
limiting the total cost the company can afford for leasing towers, alongside a
target value representing the desired total value in terms of the number of
customers served.

In the subsequent sections, we first present a brief overview of the efforts
made in the realm of the Vertex Cover problem in Section 1.2. We formally
define the problems in Section 2. We show the classical NP Completeness
results in Section 3. We develop polynomial time approximation algorithms and
a fixed parameter tractable algorithm in Section 4 and Section 5 respectively.
We conclude our efforts in Section 6.

###  1.1 Contributions

We study the computational complexity of the problems Vertex Cover Knapsack,
Vertex Cover Knapsack with Budget, Minimum Vertex Cover Knapsack, and Minimal
Vertex Cover Knapsack. For each of these problems, we resolve their complexity
with respect to general graphs and trees. We design a polynomial time
2-approximation algorithm for the problem using primal dual method. Further we
also demonstrate that the Vertex Cover Knapsack, Minimum Vertex Cover Knapsack
and Minimal Vertex Cover Knapsack all admit fixed parameter tractable
algorithms with treewidth as the parameter. Our main contributions are
highlighted in Table 1.

Vertex Cover Knapsack |  strongly $\mathsf{NP}$-complete (Theorem 3.2) pseudo-polynomial for trees (Corollary 5.7) $2^{\mathcal{O}(\text{tw})}\cdot n\cdot{\sf min}\\{s,d\\}$ (Theorem 5.1)
---|---
Vertex Cover Knapsack with Budget |  strongly $\mathsf{NP}$-complete (Theorem 3.4) pseudo-polynomial for trees (Corollary 5.3) $\mathcal{O}(n^{2}\cdot min\\{s,(\alpha(\mathcal{V}))\\})$ (Corollary 5.3)
Minimum Vertex Cover Knapsack |  $\mathsf{NP}$ hard (Observation 3.3) $\mathsf{NP}$-complete for trees $4^{\mathcal{O}(\text{tw})}\cdot n\cdot{\sf min}\\{s,d\\}$ (Theorem 5.4)
Minimal Vertex Cover Knapsack |  strongly $\mathsf{NP}$-complete (Theorem 3.6) $\mathsf{NP}$-complete for trees (Theorem 3.8) no poly-time approx. algorithm (Theorem 4.19) $8^{\mathcal{O}(\text{tw})}\cdot n\cdot{\sf min}\\{s,d\\}$ (Theorem 5.5)
Set Cover Knapsack with target value |  poly-time f-approx. algorithm (Theorem 4.9) poly-time $H_{g}$-approx algorithm (Theorem 4.12)
Set Cover Knapsack with budgeted weight |  no poly-time approx. algorithm (Theorem 4.15)
d-Hitting Set Knapsack with target value |  poly-time d-approx. algorithm (Corollary 4.11)
d-Hitting Set Knapsack with budgeted weight |  no poly-time approx. algorithm (Corollary 4.17)
Vertex Cover Knapsack with target value |  poly-time 2-approx. algorithm (Corollary 4.14)
Vertex Cover Knapsack with budgeted weight |  no poly-time approx. algorithm (Corollary 4.18)
Table 1: Summary of results

###  1.2 Related Work

Vertex Cover is a well-studied $\mathsf{NP}$-complete problem in Graph Theory.
Given a graph $\mathcal{G}$ = ($\mathcal{V}$, $\mathcal{E}$), a vertex cover
for G is any subset $\mathcal{V}^{\prime}\subseteq\mathcal{V}$ that contains
at least one endpoint from every edge. The problem is also investigated to be
$\mathsf{NP}$-complete in planar graphs with a degree at most 3 [19][20].
Weighted Vertex Cover (WVC) is the weighted version studied in different
literature where the sum of weights of all the vertices in a Vertex Cover must
be $\leqslant c$ (where $c\in\mathbb{R^{+}}$). If all the weights of the
vertices are $1$, it is called Unweighted Vertex Cover (UVC). In the paper
[25], Niedermeier and Rossmanith proved that WVC is fixed-parameter tractable
if the weights are positive integers or real numbers $\geqslant 1$, but it is
not fixed-parameter tractable if the weights are positive real numbers unless
$\textbf{P}=\mathsf{NP}$. They used a dynamic programming algorithm with
complexity $\mathcal{O}((1.3788)^{c}+cn)$, where $n$ is the number of vertices
of the input graph. Later, Fomin et al [17] provided an algorithm to improve
the running time to $\mathcal{O}((1.357)^{c}\cdot n)$ . Chlebíka and
Chlebíková [7] proposed an exact algorithm by using the crown reduction
technique for solving the Minimum Weighted Vertex Cover (MWVC) problem, whose
decision version is WVC. Approximation algorithms for MWVC are described here
[1]. Linear time 2-approximation algorithms exist for both UVC [29] and WVC
[3]. These results become improved with a better approximation factor for UVC
[23] and WVC [4]

k-Vertex Cover (the decision version of the Minimum Vertex Cover problem)
finds a vertex cover of size at most $k$ (where $k\in\mathbb{Z^{+}}$) or
returns that no such size of Vertex Cover exists. This problem is
$\mathsf{FPT}$. The first $\mathsf{FPT}$ algorithm for this problem with a
time complexity of $\mathcal{O}(2^{k}\cdot n)$ was given by Downey and Fellows
[12]. They used the technique of bounded search trees. S. Buss [12] proved
that this problem is solvable in $\mathcal{O}(k^{k}+n)$ time. The algorithm
developed by Papadimitriou and Yannakakis [28] has a running time of
$\mathcal{O}(3^{k}\cdot n)$. In the paper [2], Balasubramanian et al. gave an
algorithm with a running time of $\mathcal{O}((1.324718)^{k}\cdot k^{2}+kn)$
using bounded search techniques. Downey et al.[11] developed an algorithm
using kernelization and search tree methods with a complexity of
$\mathcal{O}((1.31951)^{k}\cdot k^{2}+kn)$. Later, Niedermeier and
Rossmanith[24] provided an algorithm with complexity
$\mathcal{O}((1.29175)^{k}\cdot k^{2}+kn)$. Another $\mathsf{FPT}$ algorithm
with a running time of $\mathcal{O}(\max{(1.25542)^{k}\cdot
k^{2},(1.2906)^{k}\cdot k}+kn)$ was given by Stege and Fellows [15]. The best-
known result, provided by Harris and Narayanaswamy [21], gives an algorithmic
complexity of $\mathcal{O}((1.25284)^{k}+kn)$.

Maximum Minimal Vertex Cover (MMVC) is a problem of finding a minimal Vertex
Cover of cardinality at least $k$. This problem admits a polynomial kernel in
terms of the number of vertices and can be solved in $\mathcal{O}(2^{k}+p(n))$
time using a search tree algorithm, where $p$ is some polynomial [16]. Later,
Peter Damaschke [9] proved that MMVC is solvable in time
$\mathcal{O}^{(}1.62^{k})$. For general graphs, Boria et al [5] showed that
this problem is polynomially approximable within the ratio $n^{-1/2}$ and
inapproximable within the ratio $n^{\varepsilon-1/2}$ unless
$\textbf{P}=\mathsf{NP}$, where $\varepsilon>0$. They proved that this problem
is FPT and can be solved in $\mathcal{O}^{(}1.5739^{opt})$ with respect to the
cardinality of the optimal solution ($opt$), in $\mathcal{O}^{*}(2.8284^{M})$
with respect to the size of the maximum matching ($M$), and also with respect
to the treewidth.

Various approximation algorithms have been explored for the Set Cover problem
like $f$ factor, $\log n$ and $\log d$, factor approximation ratios [30]. Here
$n$ and $d$ denote the number of elements in the universe and frequency of the
most frequent element respectively. Delbot and Laforest in [10] concluded that
we cannot hope to have an approximation algorithm for vertex cover better than
2.

There are several other variations of the classical Vertex Cover problem
studied in the literature, such as Connected Vertex Cover in [22], [14], and
Eternal Connected Vertex Cover in [26], [18]. In this study, we explore a
novel variant of the Vertex Cover problem, namely Vertex Cover Knapsack. Given
an undirected weighted graph $\mathcal{G}$, the size of the knapsack, and a
target value, the computational question is to compute a vertex cover that
yields the maximum profit without exceeding the size of the knapsack. We
formally define the problem in Section 2. Our main results prove that this
problem is $\mathsf{NP}$-complete.

##  2 Preliminaries

######  Definition 2.1 (Vertex Cover Knapsack).

Given an undirected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, weight of
vertices $(w(u))_{u\in\mathcal{V}}$, value of vertices
$(\alpha(u))_{u\in\mathcal{V}}$, size $s$ of knapsack, and target value $d$,
compute if there exists a subset $\mathcal{U}\subseteq\mathcal{V}$ of vertices
such that:

  1. 1.

$\mathcal{U}$ is a vertex cover.

  2. 2.

$w(\mathcal{U})=\sum_{u\in\mathcal{U}}w(u)\leqslant s$,

  3. 3.

$\alpha(\mathcal{U})=\sum_{u\in\mathcal{U}}\alpha(u)\geqslant d$

We denote an arbitrary instance of Vertex Cover Knapsack by
$(\mathcal{G},(w(u))_{u\in\mathcal{V}},(\alpha(u))_{u\in\mathcal{V}},s,d)$.

######  Definition 2.2 (Vertex Cover Knapsack with Budget).

Given an undirected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, weight of
vertices $(w(u))_{u\in\mathcal{V}}$, value of vertices
$(\alpha(u))_{u\in\mathcal{V}}$, budget $k$ of the vertex cover, size $s$ of
knapsack, and target value $d$, compute if there exists a subset
$\mathcal{U}\subseteq\mathcal{V}$ of vertices such that:

  1. 1.

$\mathcal{U}$ is a Vertex Cover of size at most $k$,

  2. 2.

$w(\mathcal{U})=\sum_{u\in\mathcal{U}}w(u)\leqslant s$,

  3. 3.

$\alpha(\mathcal{U})=\sum_{u\in\mathcal{U}}\alpha(u)\geqslant d$

We denote an arbitrary instance of Vertex Cover Knapsack with Budget by
$(\mathcal{G},(w(u))_{u\in\mathcal{V}},(\alpha(u))_{u\in\mathcal{V}},s,d,k)$.

######  Definition 2.3 (Minimum Vertex Cover Knapsack).

Given an undirected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, weight of
vertices $(w(u))_{u\in\mathcal{V}}$, value of vertices
$(\alpha(u))_{u\in\mathcal{V}}$, size $s$ of knapsack, and target value $d$,
compute if there exists a subset $\mathcal{U}\subseteq\mathcal{V}$ of vertices
such that:

  1. 1.

$\mathcal{U}$ is minimum Vertex Cover,

  2. 2.

$w(\mathcal{U})=\sum_{u\in\mathcal{U}}w(u)\leqslant s$,

  3. 3.

$\alpha(\mathcal{U})=\sum_{u\in\mathcal{U}}\alpha(u)\geqslant d$

We denote an arbitrary instance of Minimum Vertex Cover Knapsack by
$(\mathcal{G},(w(u))_{u\in\mathcal{V}},(\alpha(u))_{u\in\mathcal{V}},s,d)$.

######  Definition 2.4 (Minimal Vertex Cover Knapsack).

Given an undirected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, weight of
vertices $(w(u))_{u\in\mathcal{V}}$, value of vertices
$(\alpha(u))_{u\in\mathcal{V}}$, size $s$ of knapsack, and target value $d$,
compute if there exists a subset $\mathcal{U}\subseteq\mathcal{V}$ of vertices
such that:

  1. 1.

$\mathcal{U}$ is a minimal Vertex Cover,

  2. 2.

$w(\mathcal{U})=\sum_{u\in\mathcal{U}}w(u)\leqslant s$,

  3. 3.

$\alpha(\mathcal{U})=\sum_{u\in\mathcal{U}}\alpha(u)\geqslant d$

We denote an arbitrary instance of Minimal Vertex Cover Knapsack by
$(\mathcal{G},(w(u))_{u\in\mathcal{V}},(\alpha(u))_{u\in\mathcal{V}},s,d)$.

######  Definition 2.5 (Treewidth).

Let $G=(V_{G},E_{G})$ be a graph. A tree-decomposition of a graph $G$ is a
pair
$(\mathbb{T}=((V_{\mathbb{T}},E_{\mathbb{T}}),\mathcal{X}=\\{X_{t}\\}_{t\in
V_{\mathbb{T}}})$, where ${\mathbb{T}}$ is a tree where every node $t\in
V_{\mathbb{T}}$ is assigned a subset $X_{t}\subseteq V_{G}$, called a bag,
such that the following conditions hold.

  * $\vartriangleright$

$\bigcup_{t\in V_{\mathbb{T}}}{X_{t}}=V_{G}$,

  * $\vartriangleright$

for every edge $\\{x,y\\}\in E_{G}$ there is a $t\in V_{\mathbb{T}}$ such that
$x,y\in X_{t}$, and

  * $\vartriangleright$

for any $v\in V_{G}$ the subgraph of $\mathbb{T}$ induced by the set $\\{t\mid
v\in X_{t}\\}$ is connected.

The width of a tree decomposition is $\max_{t\in V_{\mathbb{T}}}|X_{t}|-1$.
The treewidth of $G$ is the minimum width over all tree decompositions of $G$
and is denoted by $\text{tw}(G)$.

A tree decomposition $(\mathbb{T},\mathcal{X})$ is called a nice edge tree
decomposition if $\mathbb{T}$ is a tree rooted at some node $r$ where
$X_{r}=\emptyset$, each node of $\mathbb{T}$ has at most two children, and
each node is of one of the following kinds:

  * $\vartriangleright$

Introduce node: a node $t$ that has only one child $t^{\prime}$ where
$X_{t}\supset X_{t^{\prime}}$ and $|X_{t}|=|X_{t^{\prime}}|+1$.

  * $\vartriangleright$

Forget vertex node: a node $t$ that has only one child $t^{\prime}$ where
$X_{t}\subset X_{t^{\prime}}$ and $|X_{t}|=|X_{t^{\prime}}|-1$.

  * $\vartriangleright$

Join node: a node $t$ with two children $t_{1}$ and $t_{2}$ such that
$X_{t}=X_{t_{1}}=X_{t_{2}}$.

  * $\vartriangleright$

Leaf node: a node $t$ that is a leaf of $\mathbb{T}$, and $X_{t}=\emptyset$.

We additionally require that every edge is introduced exactly once. One can
show that a tree decomposition of width $t$ can be transformed into a nice
tree decomposition of the same width $t$ and with $\mathcal{O}(t|V_{G}|)$
nodes [8]. For a node $t\in\mathbb{T}$, let $\mathbb{T}_{t}$ be the subtree of
$\mathbb{T}$ rooted at $t$, and $V(\mathbb{T}_{t})$ denote the vertex set in
that subtree. Then $G_{t}$ is the subgraph of $G$ where the vertex set is
$\bigcup_{t^{\prime}\in V(\mathbb{T}_{t})}X_{t^{\prime}}$ and the edge set is
the union of the set of edges introduced in each $t^{\prime},t^{\prime}\in
V(\mathbb{T}_{t})$. We denote by $V(G_{t})$ the set of vertices in that
subgraph, and by $E(G_{E})$ the set of edges of the subgraph.: a node $t$ that
is a leaf of $\mathbb{T}$, and $X_{t}=\emptyset$.

In this paper, we sometimes fix a vertex $v\in V_{G}$ and include it in every
bag of a nice edge tree decomposition $(\mathbb{T},\mathcal{X})$ of $G$, with
the effect of the root bag and each leaf bag containing $v$. For the sake of
brevity, we also call such a modified tree decomposition a nice tree
decomposition. Given the tree $\mathbb{T}$ rooted at the node $r$, for any
nodes $t_{1},t_{2}\in V_{\mathbb{T}}$, the distance between the two nodes in
$\mathbb{T}$ is denoted by $\sf{dist}_{\mathbb{T}}(t_{1},t_{2})$.

##  3 Results: Classical NP Completeness

######  Definition 3.1 (Vertex Cover).

Given a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ and a positive integer
$k$, compute if there exists a subset
$\mathcal{V}^{\prime}\subseteq\mathcal{V}$ such that at least one end-point of
every edge belongs to $\mathcal{V}^{\prime}$ and
$|\mathcal{V}^{\prime}|\leqslant k$. We denote an arbitrary instance of Vertex
Cover by $(\mathcal{G},k)$.

In this section, we show that Vertex Cover Knapsack is strongly
$\mathsf{NP}$-complete by reducing it from Vertex Cover (see, Definition 3.1).

######  Theorem 3.2.

Vertex Cover Knapsack is strongly $\mathsf{NP}$-complete for general graph.

######  Proof 3.3.

Clearly, Vertex Cover Knapsack $\in$ $\mathsf{NP}$. We reduce Vertex Cover to
Vertex Cover Knapsack to prove NP-hardness. Let
$(\mathcal{G}(\mathcal{V}=\\{v_{i}:i\in[n]\\},\mathcal{E}),k)$ be an arbitrary
instance of Vertex Cover of size $k$. We construct the following instance
$(\mathcal{G}^{\prime}(\mathcal{V}^{\prime}=\\{u_{i}:i\in[n]\\},\mathcal{E}^{\prime}),(w(u))_{u\in\mathcal{V}^{\prime}},(\alpha(u))_{u\in\mathcal{V}^{\prime}},s,d)$
of Vertex Cover Knapsack.

$\displaystyle\mathcal{V}^{\prime}=\\{u_{i}:v_{i}\in\mathcal{V},\forall
i\in[n]\\}$
$\displaystyle\mathcal{E}^{\prime}=\\{\\{u_{i},u_{j}\\}:\\{v_{i},v_{j}\\}\in\mathcal{E},i\neq
j,\forall i,j\in[n]\\}$ $\displaystyle w(u_{i})=1,\alpha(u_{i})=1\qquad\forall
i\in[n]$ $\displaystyle s=d=k$

The Vertex Cover Knapsack problem has a solution iff Vertex Cover has a
solution.

Let
$(\mathcal{G}^{\prime},(w(u))_{u\in\mathcal{V}^{\prime}},(\alpha(u))_{u\in\mathcal{V}^{\prime}},s,d)$
of Vertex Cover Knapsack such that $\mathcal{W}^{\prime}$ be the resulting
subset of $\mathcal{V}^{\prime}$ with (i) $\mathcal{W}^{\prime}$ is a Vertex
Cover, (ii) $\sum_{u\in\mathcal{W}^{\prime}}w(u)=k$, (iii)
$\sum_{u\in\mathcal{W}^{\prime}}\alpha(u)=k$
This means that the set $\mathcal{W}^{\prime}$ is a Vertex Cover which gives
the maximum profit $k$ for the bag capacity of size $k$. In other words,
$\mathcal{W}^{\prime}$ is a Vertex Cover of size $k$. Since
$\mathcal{W}^{\prime}=\\{u_{i}:v_{i}\in\mathcal{W},\forall i\in[n]\\}$,
$\mathcal{W}$ is a Vertex Cover of size $k$. Therefore, the Vertex Cover
instance is an yes instance.

Conversely, let us assume that Vertex Cover instance $(\mathcal{G},k)$ is an
yes instance.
Then there exists a subset $\mathcal{W}\subseteq\mathcal{V}$ of size $k$ such
that it outputs a Vertex Cover.
Consider the set $\mathcal{W}^{\prime}=\\{u_{i}:v_{i}\in\mathcal{W},\forall
i\in[n]\\}$. Since each vertex of $\mathcal{W}^{\prime}$ is involved with
weight 1 and produces profit amount 1, $\mathcal{W}^{\prime}$ is a Vertex
Cover of max bag size and total profit $k$. Therefore, the Vertex Cover
Knapsack instance is an yes instance.

###  3.1 Vertex Cover Knapsack with Budget

In this section, we show that Vertex Cover Knapsack with Budget is strongly
$\mathsf{NP}$-complete by reducing it from Vertex Cover (see, definition 3.1).

######  Theorem 3.4.

Vertex Cover Knapsack with Budget is strongly $\mathsf{NP}$-complete for
general graph.

######  Proof 3.5.

Clearly, Vertex Cover Knapsack with Budget $\in$ $\mathsf{NP}$. We reduce
Vertex Cover to Vertex Cover Knapsack with Budget to prove NP-hardness. Let
$(\mathcal{G}(\mathcal{V}=\\{v_{i}:i\in[n]\\},\mathcal{E}),k)$ be an arbitrary
instance of Vertex Cover of size $k$. We construct the following instance
$(\mathcal{G}^{\prime}(\mathcal{V}^{\prime}=\\{u_{i}:i\in[n]\\},\mathcal{E}^{\prime}),(w(u))_{u\in\mathcal{V}^{\prime}},(\alpha(u))_{u\in\mathcal{V}^{\prime}},s,d,k^{\prime})$
of Vertex Cover Knapsack with Budget.

$\displaystyle\mathcal{V}^{\prime}=\\{u_{i}:v_{i}\in\mathcal{V},\forall
i\in[n]\\}$
$\displaystyle\mathcal{E}^{\prime}=\\{\\{u_{i},u_{j}\\}:\\{v_{i},v_{j}\\}\in\mathcal{E},i\neq
j,\forall i,j\in[n]\\}$ $\displaystyle w(u_{i})=1,\alpha(u_{i})=1\qquad\forall
i\in[n]$ $\displaystyle s=d=k^{\prime}=k$

The Vertex Cover Knapsack with Budget problem has a solution iff Vertex Cover
has a solution.
Let
$(\mathcal{G}^{\prime}(\mathcal{V}^{\prime},\mathcal{E}^{\prime}),(w(u))_{u\in\mathcal{V}^{\prime}},(\alpha(u))_{u\in\mathcal{V}^{\prime}},s,d,k^{\prime})$
of Vertex Cover Knapsack with Budget such that $\mathcal{W}^{\prime}$ be the
resulting subset of $\mathcal{V}^{\prime}$ with (i) $\mathcal{W}^{\prime}$ is
a Vertex Cover of size at most $k^{\prime}$, (ii)
$\sum_{u\in\mathcal{W}^{\prime}}w(u)\leqslant s=k^{\prime}$, (iii)
$\sum_{u\in\mathcal{W}^{\prime}}\alpha(u)\geqslant d=k^{\prime}$.
This means that the set $\mathcal{W}^{\prime}$ is a Vertex Cover which gives
the maximum profit $k^{\prime}$ for the bag capacity of $k^{\prime}$. Now,
since $k^{\prime}=k$ and
$\mathcal{W}^{\prime}=\\{u_{i}:v_{i}\in\mathcal{W},\forall i\in[n]\\}$ , we
can say that $\mathcal{W}$ is a Vertex Cover of size $k$. Therefore, the
Vertex Cover instance is an yes instance.

Conversely, let us assume that Vertex Cover instance $(\mathcal{G},k)$ is an
yes instance.
Then there exists a subset $\mathcal{W}\subseteq\mathcal{V}$ of size $k$ such
that it outputs a Vertex Cover.
Since $\mathcal{W}^{\prime}=\\{u_{i}:v_{i}\in\mathcal{W},\forall i\in[n]\\}$
and each vertex of $\mathcal{W}^{\prime}$ is involved with weight 1 and
produces profit amount 1 in the reduced graph $\mathcal{G}^{\prime}$,
$\mathcal{W}^{\prime}$ is a Vertex Cover of max bag size and total profit $k$.
Also we have, $k=k^{\prime}$. Therefore, the Vertex Cover Knapsack with Budget
instance is an yes instance.

###  3.2 Minimal Vertex Cover Knapsack

We show that Minimal Vertex Cover Knapsack is strongly $\mathsf{NP}$-complete
by reducing it from Maximum Minimal Vertex Cover which is a
$\mathsf{NP}$-complete problem.

######  Theorem 3.6.

Minimal Vertex Cover Knapsack is strongly $\mathsf{NP}$-complete for general
graph.

######  Proof 3.7.

Clearly, Minimal Vertex Cover Knapsack $\in$ $\mathsf{NP}$. Since, the
decision version of Maximum Minimal Vertex Cover is $\mathsf{NP}$-complete, we
reduce Maximum Minimal Vertex Cover to Minimal Vertex Cover Knapsack to prove
NP-completeness. Let
$(\mathcal{G}(\mathcal{V}=\\{v_{i}:i\in[n]\\},\mathcal{E}),k)$ be an arbitrary
instance of Maximum Minimal Vertex Cover of size $k$. We construct the
following instance
$(\mathcal{G}^{\prime}(\mathcal{V}^{\prime}=\\{u_{i}:i\in[n]\\},\mathcal{E}^{\prime}),(w(u))_{u\in\mathcal{V}^{\prime}},(\alpha(u))_{u\in\mathcal{V}^{\prime}},s,d)$
of Minimal Vertex Cover Knapsack.

$\displaystyle\mathcal{V}^{\prime}=\\{u_{i}:v_{i}\in\mathcal{V},\forall
i\in[n]\\}$
$\displaystyle\mathcal{E}^{\prime}=\\{\\{u_{i},u_{j}\\}:\\{v_{i},v_{j}\\}\in\mathcal{E},i\neq
j,\forall i,j\in[n]\\}$ $\displaystyle
w(u_{i})=1,w(u_{j})=0\quad\text{for\leavevmode\nobreak\
some\leavevmode\nobreak\ }i,j\in[1,n]$
$\displaystyle\alpha(u_{i})=1\quad\forall i\in[1,n]$ $\displaystyle s=d=k$

The reduction of Maximum Minimal Vertex Cover to Minimal Vertex Cover Knapsack
works in polynomial time. The Minimal Vertex Cover Knapsack problem has a
solution iff Maximum Minimal Vertex Cover has a solution.
Let
$(\mathcal{G}^{\prime}(\mathcal{V}^{\prime},\mathcal{E}^{\prime}),(w(u))_{u\in\mathcal{V}^{\prime}},(\alpha(u))_{u\in\mathcal{V}^{\prime}},s,d)$
of Minimal Vertex Cover Knapsack such that $\mathcal{W}$ be the resulting
subset of $\mathcal{V}^{\prime}$ with (i) $\mathcal{W}$ is a minimal Vertex
Cover, (ii) $\sum_{u\in\mathcal{W}}w(u)\leqslant s=k$, (iii)
$\sum_{u\in\mathcal{W}}\alpha(u)\geqslant d=k$.
From the above condition (i), as $\mathcal{W}$ is minimal Vertex Cover we can
not remove any vertex from $\mathcal{W}$ which gives another Vertex Cover.
Now, since we rewrite the second and third conditions as
$|\mathcal{W}|\leqslant k$ and $|\mathcal{W}|\geqslant k$. So, $|\mathcal{W}|$
must be $k$. Now, let $\mathcal{I}=\\{v_{i}:u_{i}\in\mathcal{W},\forall
i\in[n]\\}$. Since $\mathcal{W}$ is the Minimal Vertex Cover of size $k$, then
$\mathcal{I}(\subseteq\mathcal{V})$ must be Maximum Minimal Vertex Cover set
of size at least $k$.Therefore, the Maximum Minimal Vertex Cover instance is
an yes instance.

Conversely, let us assume that Maximum Minimal Vertex Cover instance
$(\mathcal{G},k)$ is an yes instance.
Then there exists a subset $\mathcal{I}\subseteq\mathcal{V}$ of size
$\geqslant k$ such that it outputs an Maximum Minimal Vertex Cover. Let
$\mathcal{W}=\\{u_{i}:v_{i}\in\mathcal{I},\forall i\in[n]\\}$. Since
$\mathcal{I}$ is an Maximum Minimal Vertex Cover of size $\geqslant k$, then
$\mathcal{W}$ must be a Minimal Vertex Cover of size $k$. So,
$\sum_{u\in\mathcal{W}}w(u)\leqslant k=s$ and
$\sum_{u\in\mathcal{W}}\alpha(u)\geqslant k=d$. Now, we want to prove that
$\mathcal{W}$ is a minimal Vertex Cover.
Therefore, the Minimal Vertex Cover Knapsack instance is an yes instance.

######  Theorem 3.8.

Minimal Vertex Cover Knapsack is $\mathsf{NP}$-complete for trees.

######  Proof 3.9.

Clearly, Minimal Vertex Cover Knapsack for tree $\in$ NP. We reduce Minimal
Vertex Cover Knapsack from Knapsack to prove hardness. Given, an arbitrary
instance
$(\mathcal{X},(\theta_{i})_{i\in\mathcal{X}},(p_{i})_{i\in\mathcal{X}},b,q)$
of Knapsack, we create an instance of Minimal Vertex Cover Knapsack for trees
by forming a complete binary tree $\mathcal{T}$ = ($\mathcal{V}$,
$\mathcal{E}$) that has $n$ nodes in its penultimate level and denote an
instance as
$(\mathcal{T},(w(u))_{u\in\mathcal{T}},(\alpha(u))_{u\in\mathcal{T}},s,d)$.
The construction steps is as follows:

  1. 1.

We construct a complete binary tree $\mathcal{T}$ such that the penultimate
level of this tree has $n$ nodes representing the $n$ items.

  2. 2.

Without loss of generality we assume, that $n=|\mathcal{X}|=2^{k}$ because
suppose there exists $n$ such that $2^{k-1}<n<2^{k}$, add $2^{k}-n$ items to
$\mathcal{X}$ each with size = 0 and profit = 0, where $k\geqslant 0$.

  3. 3.

Let $\mathcal{V}^{\prime}\subseteq\mathcal{T}[\mathcal{V}]$ denote the
vertices belonging to the penultimate level of the tree $\mathcal{T}$.

  4. 4.

Set
$w(u_{i})_{u_{i}\in\mathcal{V}^{\prime}}=\theta_{i},\alpha(u_{i})_{u_{i}\in\mathcal{V}^{\prime}}=p_{i},w(u_{i})_{u_{i}\in\mathcal{V}-\mathcal{V}^{\prime}}=0,\alpha(u_{i})_{u_{i}\in\mathcal{V}-\mathcal{V}^{\prime}}=0\\\
s=b,d=q$

This construction takes polynomial time.

We now show that Knapsack $\leqslant_{p}$ Minimal Vertex Cover Knapsack.

The Minimal Vertex Cover Knapsack problem has a solution if and only if
Knapsack has a solution.

Minimal Vertex Cover Knapsack ➞ Knapsack
Let $(\mathcal{T},(w(u))_{u\in\mathcal{V}},(\alpha(u))_{u\in\mathcal{V}},s,d)$
be an instance of Minimal Vertex Cover Knapsack such that $\mathcal{W}$ be the
resulting subset of $\mathcal{V}$ with

  1. 1.

$\mathcal{W}$ is a minimal Vertex Cover,

  2. 2.

$\sum_{u\in\mathcal{W}}w(u)=b$,

  3. 3.

$\sum_{u\in\mathcal{W}}\alpha(u)=d$

This means that the set $\mathcal{W}$ is a minimal Vertex Cover, which gives
the maximum profit $d$ for the bag capacity of size $b$. In other words,
$\mathcal{W}\cap\mathcal{V}^{\prime}=\mathcal{W}^{\prime}\neq\phi$ i.e.
$\mathcal{W}$ must contain at least a subset of $\mathcal{V}^{\prime}$ in
order to attain the required profit $d$ because $\mathcal{W}$\- $\mathcal{V}$’
has vertices whose weight = 0, and profit = 0. As per our construction,
$\mathcal{V}$’ contains the vertices denoting the $n$ items of $\mathcal{X}$
in Knapsack. Therefore, the Knapsack instance is an yes instance.

Knapsack ➞ Minimal Vertex Cover Knapsack
Let
$(\mathcal{X},(\theta_{i})_{i\in\mathcal{X}},(p_{i})_{i\in\mathcal{X}},b,q)$
be an instance of Knapsack such that $\mathcal{I}$ be the resulting subset of
$\mathcal{X}$ with

  1. 1.

$\sum_{i\in\mathcal{I}}\theta_{i}\leqslant b$,

  2. 2.

$\sum_{i\in\mathcal{I}}p_{i}\geqslant q$

The minimal vertex cover knapsack must pick vertices from
$\mathcal{V}^{\prime}$ otherwise it cannot meet the desired value $d$ as all
vertices of $\mathcal{V}-\mathcal{V}^{\prime}$ have weight and value equal to
0.

We obtain a minimal Vertex Cover for $\mathcal{T}$ by recursively constructing
the solution set, $\mathcal{W}$ as:

  1. 1.

if $u\in\mathcal{T}[\mathcal{I}]$, include $u$ in $\mathcal{W}$ and delete
$\mathcal{N}[u]$ from $\mathcal{T}$

  2. 2.

if $u\notin\mathcal{T}[\mathcal{I}]$, include $\mathcal{N}(u$ in $\mathcal{W}$
delete $\mathcal{N}[u]$ from $\mathcal{T}$

  3. 3.

solve for minimal vertex cover on the induced sub-graph where weight and
profit associated with each vertex is 0.

Therefore, the Minimal Vertex Cover Knapsack for tree is an yes instance.

###  3.3 Minimum Vertex Cover Knapsack

This problem is not known to be in $\mathsf{NP}$, even the decision version of
this problem for the general graph.

##  4 Results: Polynomial Time Approximation Algorithms

In this section, we define optimization versions of the Vertex Cover Knapsack
problem. We consider the following two versions:

######  Definition 4.1 (Vertex Cover Knapsack with target value).

Given an undirected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, weight of
vertices $(w(u))_{u\in\mathcal{V}}$, value of vertices
$(\alpha(u))_{u\in\mathcal{V}}$, and target value $d$, compute a subset
$\mathcal{U}\subseteq\mathcal{V}$ of vertices that minimizes the total weight
$w(\mathcal{U})=\sum_{u\in\mathcal{U}}w(u)$ such that:

  1. 1.

$\mathcal{U}$ is a vertex cover.

  2. 2.

$\alpha(\mathcal{U})=\sum_{u\in\mathcal{U}}\alpha(u)\geqslant d$

######  Definition 4.2 (Vertex Cover Knapsack with budgeted weight).

Given an undirected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, weight of
vertices $(w(u))_{u\in\mathcal{V}}$, value of vertices
$(\alpha(u))_{u\in\mathcal{V}}$, and size $s$ of knapsack, compute a subset
$\mathcal{U}\subseteq\mathcal{V}$ of vertices that maximizes the total value
$\alpha(\mathcal{U})=\sum_{u\in\mathcal{U}}\alpha(u)$such that:

  1. 1.

$\mathcal{U}$ is a vertex cover.

  2. 2.

$w(\mathcal{U})=\sum_{u\in\mathcal{U}}w(u)\leqslant s$,

We formulate Vertex Cover Knapsack with target value problem as the following
integer linear programming, in which the primal variable $x_{i}$ indicates
whether vertex $v_{i}\in\mathcal{V}$ is chosen to be in the solution or not:

minimize $\sum_{u\in\mathcal{V}}w(u)x_{u}$

Subject to: $\displaystyle x_{u}+x_{v}\geqslant 1,\forall(u,v)\in\mathcal{E}$
$\displaystyle\sum_{u\in\mathcal{V}}\alpha(u)x_{u}\geqslant d$ $\displaystyle
x_{u}\in\\{0,1\\},\forall u\in\mathcal{V}$

We replace the constraints $x_{u}\in\\{0,1\\}$, with $x_{u}\geqslant 0$,
$\forall u\in\mathcal{V}$ to obtain linear programming relaxation of the
integer linear program. The relaxed linear programming of the above integer
linear programming has an unbounded integrality gap. Consider an edgeless
graph $\mathcal{G}$ ($\mathcal{V}$, $\mathcal{E}$) such that
$\mathcal{E}=\emptyset$. Let $\mathcal{V}=\\{v_{1},v_{2}\\}$, $w(v_{1})=0$,
$w(v_{2})=1$, $\alpha(v_{1})=d-1$ and $\alpha(v_{2})=d$. The optimal solution
to integer linear programming sets $x_{v_{1}}=0,x_{v_{2}}=1$, for a total
weight of 1. However, the solution to the relaxed linear programming sets
$x_{v_{1}}=1,x_{v_{2}}=1/d$ and has total weight of 1/d. Thus, in this case
the integrality gap is at least $\frac{1}{1/d}=d$. We also consider a
generalized version of Vertex Cover problem i.e. Set Cover problem.

######  Definition 4.3 (Set Cover).

Given a universe $\mathcal{U}$ of $n$ elements and some subsets
$\SS_{1},\SS_{2},\dots,\SS_{m}$ where each $\SS_{i}\subseteq\mathcal{U}$, and
a non negative weight $w(i)\geqslant 0$ for each subset $\SS_{i}$, $\forall
i\in[m]$. The goal is to find $\mathcal{I}\subseteq\\{1,2,\dots,m\\}$ that
minimizes $\sum_{i\in\mathcal{I}}w(i)$ subject to
$\bigcup_{i\in\mathcal{I}}\SS_{i}=\mathcal{U}$ .

Vertex cover is a special case of set cover. Interestingly, if each set
$\SS_{i}$, $\forall i\in[m]$, is assigned with a non-negative value in
addition to weight, and we look for a solution to the Set Cover that not only
minimizes the weight but also maximizes the value, then we call this problem
as Set Cover Knapsack. Now it is easy to see that, Set Cover Knapsack problem
is also $\mathsf{NP}$-complete and hence we cannot hope to have a
deterministic polynomial time algorithm unless $P\neq\mathsf{NP}$. The
optimization versions of the Set Cover Knapsack problem are Set Cover Knapsack
with target value and Set Cover Knapsack with budgeted weight. In Set Cover
Knapsack with target value, the desired solution must be a solution to the Set
Cover problem and must meet the desired value, say $d$ with minimum weight. On
the other hand, the solution to the Set Cover Knapsack with budgeted weight
problem, must maximize the value while not exceeding the given weight, say
$s$. We formally define the problems below.

######  Definition 4.4 (Set Cover Knapsack with target value).

Given a universe $\mathcal{U}$ of $n$ elements and a family of subsets
$\mathcal{F}=\\{1,2,\dots,m\\}$ where each $\SS_{i}\subseteq\mathcal{U}$,
$\forall i\in[m]$ and a non negative weight $w(i)\geqslant 0$ and value
$\alpha(i)\geqslant 0$ for each subset $\SS_{i}$, $\forall i\in[m]$. The goal
is to find $\mathcal{I}\subseteq\\{1,2,\dots,m\\}$ that minimizes
$\sum_{i\in\mathcal{I}}w(i)$ subject to
$\bigcup_{i\in\mathcal{I}}\SS_{i}=\mathcal{U}$ such that the total value is at
least $d$.

######  Definition 4.5 (Set Cover Knapsack with budgeted weight).

Given a universe $\mathcal{U}$ of $n$ elements and a family of subsets
$\mathcal{F}=\\{1,2,\dots,m\\}$ where each $\SS_{i}\subseteq\mathcal{U}$,
$\forall i\in[m]$, and a non negataive weight $w(i)\geqslant 0$ and value
$\alpha(i)\geqslant 0$ for each subset $\SS_{i}$, $\forall i\in[m]$. The goal
is to find $\mathcal{I}\subseteq\\{1,2,\dots,m\\}$ that maximizes
$\sum_{i\in\mathcal{I}}\alpha(i)$ subject to
$\bigcup_{i\in\mathcal{I}}\SS_{i}=\mathcal{U}$ such that the total weight is
at most $s$.

Till now we have considered the Vertex Cover Knapsack problem for planar
graphs. We now generalise the problem for hyper-graphs using d-Hitting Set.
The d-Hitting Set problem is one of the fundamental combinatorial optimization
problems: given a set of points $\mathcal{P}$ and a set of geometric objects
$\mathcal{D}$ in the plane, the goal is to compute a small-sized subset of
$\mathcal{P}$ that hits all objects in $\mathcal{D}$ [6]. This problem
suitably capture the vertex cover problem on hyper-graphs [13].

######  Definition 4.6 (d-Hitting Set).

Given a universe $\mathcal{U}$ of $n$ elements and a family of subsets
$\mathcal{F}=\SS_{1},\SS_{2},\dots,\SS_{m}$ where each
$\SS_{i}\subseteq\mathcal{U}$ $\forall i\in[m]$, $|\SS_{i}|\leqslant$ d, and a
non negative weight $w(j)\geqslant 0$ for each element $j$, $\forall j\in[n]$.
The goal is to find $\mathcal{J}\subseteq\\{1,2,\dots,n\\}$ that minimizes
$\sum_{j\in\mathcal{J}}w(j)$ such that each subset $\SS_{i}$ is hit by some
element in $\mathcal{J}$.

It is easy to see that Set Cover is dual to d-Hitting Set, meaning that it is
exactly the same problem, i.e we are looking for a set cover in the dual set
system. There is a $\rho$ factor approximation algorithm for d-Hitting Set if
and only if there is a $\rho$ factor approximation algorithm for Set Cover
[27]. Similar to the Set Cover Knapsack, we can formulate d-Hitting Set
KNAPSACK problem. In the d-Hitting Set problem we assign values and weights to
the elements of the Universe.

######  Definition 4.7 (d-Hitting Set Knapsack with target value).

Given a universe $\mathcal{U}$ of $n$ elements and a family of subsets
$\mathcal{F}=\SS_{1},\SS_{2},\dots,\SS_{m}$ where each
$\SS_{i}\subseteq\mathcal{U}$ $\forall i\in[m]$, $|\SS_{i}|\leqslant$ d, and a
non negative weight $w(j)\geqslant 0$ and a non negative value $\alpha(j)$,
$\forall j\in[n]$. The goal is to find $\mathcal{J}\subseteq\\{1,2,\dots,n\\}$
that minimizes $\sum_{j\in\mathcal{J}}w(j)$ such that each subset $\SS_{i}$ is
hit by some element in $\mathcal{J}$ and the total value is at least $d$.

######  Definition 4.8 (d-Hitting Set Knapsack with budgeted weight).

Given a universe $\mathcal{U}$ of $n$ elements and a family of subsets
$\mathcal{F}=\SS_{1},\SS_{2},\dots,\SS_{m}$ where each
$\SS_{i}\subseteq\mathcal{U}$ $\forall i\in[m]$, $|\SS_{i}|\leqslant$ d, and a
non negative weight $w(j)\geqslant 0$ and a non negative value $\alpha(j)$,
$\forall j\in[n]$. The goal is to find $\mathcal{J}\subseteq\\{1,2,\dots,n\\}$
that maximizes $\sum_{j\in\mathcal{J}}\alpha(j)$ such that each subset
$\SS_{i}$ is hit by some element in $\mathcal{J}$ and the total weight is at
most $s$.

We now focus on the Set Cover problem due to the ease of exposition. We
formulate Set Cover Knapsack with target value problem as the following
integer linear programming, in which the primal variable $x_{i}$ indicates
whether set $\SS_{i}$ is chosen to be in the solution or not:

minimize $\sum_{i\in[m]}w(i)x_{i}$

Subject to: $\displaystyle\sum_{i:e_{j}\in\SS_{i}}x_{i}\geqslant 1,\forall
e_{j}\in\mathcal{U}$ $\displaystyle\sum_{i\in[m]}\alpha(i)x_{i}\geqslant d$
$\displaystyle x_{i}\in\\{0,1\\},\forall i\in[m]$

The above formulation has a bad integrality gap. We think of an alternative
formulation where for each subset $\mathcal{A}\subseteq\mathcal{F}$ of sets
such that $\alpha(A)=\sum_{i\in A}\alpha(i)<d$. We define the residual value
$d_{\mathcal{A}}=d-\alpha(\mathcal{A})$. Given the set $\mathcal{A}$, we
simplify the problem on the sets $\mathcal{F}-\mathcal{A}$, where the target
value is is now $d_{\mathcal{A}}$. We also reduce the value of the each set
$\SS_{i}\in\mathcal{F}-\mathcal{A}$ to be the minimum of its own value and
$d_{\mathcal{A}}$ i.e let $\alpha^{\mathcal{A}}(i)$ = min($\alpha(i)$,
$d_{\mathcal{A}}$). We can now give the following Integer linear programming
formulation of the problem:

minimize $\sum_{i\in[m]}w(i)x_{i}$

Subject to: $\displaystyle\sum_{i:e_{j}\in\SS_{i}}x_{i}\geqslant 1,\forall
e_{j}\in\mathcal{U}$
$\displaystyle\sum_{i\in\mathcal{F}-\mathcal{A}}\alpha^{\mathcal{A}}(i)x_{i}\geqslant
d_{\mathcal{A}},\forall\mathcal{A}\subseteq\mathcal{F}$ $\displaystyle
x_{i}\in\\{0,1\\},\forall i\in[m]$

We replace the constraints $x_{i}\in\\{0,1\\}$, with $x_{i}\geqslant 0$ to
obtain linear programming relaxation of the integer linear program. The dual
of the linear programming relaxation is :

maximize
$\sum_{\mathcal{A}:\mathcal{A}\subseteq\mathcal{F}}d_{\mathcal{A}}y_{\mathcal{A}}$
\+ $\sum_{j\in[n]}y_{j}$

Subject to: $\displaystyle\sum_{j:e_{j}\in\SS_{i}}y_{j}\leqslant
w(i),\forall\SS_{i}\in\mathcal{F}$
$\displaystyle\sum_{\mathcal{A}\subseteq\mathcal{F}:i\not\in\mathcal{A}}\alpha^{\mathcal{A}}(i)y_{\mathcal{A}}\leqslant
w(i),\forall i\in\mathcal{F}$ $\displaystyle y_{\mathcal{A}}\geqslant
0,\forall\mathcal{A}\subset\mathcal{F}$

We can now give a primal dual algorithm in Algorithm 1 for the Set Cover
Knapsack with target value problem by modifying the algorithm given in [30]
using the primal dual formulations given above.

Algorithm 1 Primal Dual algorithm for the Set Cover Knapsack with target value
problem

1:$y\leftarrow 0$

2:$\mathcal{A}\leftarrow\emptyset$

3:while $\alpha(\mathcal{A})<d$ do

4: Increase $y_{\mathcal{A}}$ until for some
$i\in\mathcal{F}-\mathcal{A},\sum_{\mathcal{B}\subseteq\mathcal{F}:i\not\in\mathcal{B}}\alpha^{\mathcal{B}}(i)y_{\mathcal{B}}\leqslant
w(i)$

5: $\mathcal{A}\leftarrow\mathcal{A}\cup\\{i\\}$

6:end while

7:$\mathcal{X}\leftarrow\mathcal{A}$

8:$\mathcal{A}^{\prime}\leftarrow\mathcal{A}$

9:while $\exists e_{j}\not\in\bigcup_{i\in\mathcal{A}^{\prime}}\SS_{i}$ do

10: Increase $y_{j}$ until there is some $l$ with $e_{j}\in\SS_{l}$ such that
$\sum_{j:e_{j}\in\SS_{l}}y_{j}\leqslant w(l)$

11: $\mathcal{A}^{\prime}\leftarrow\mathcal{A}\cup\\{l\\}$

12:end while

13:return $\mathcal{A}^{\prime}$

######  Theorem 4.9.

Algorithm 1 is a $f$-approximation algorithm for the Set Cover Knapsack with
target value problem, where $f$ is the frequency of the most frequent element.

######  Proof 4.10.

Let $\mathcal{A}^{\prime}$ be the output set of our algorithm that contains
the indices of the sets that are picked up. Suppose our algorithm returns
$ALG$

$\displaystyle ALG$ $\displaystyle=\sum_{i\in\mathcal{A}^{\prime}}w(i)x_{i}$
(1)
$\displaystyle=\sum_{i\in\mathcal{X}}w(i)x_{i}+\sum_{i\in\mathcal{A}^{\prime}-\mathcal{X}}w(i)x_{i}$
(2)

Let OPT be the optimal solution to the Set Cover Knapsack with target value
problem $l$ be the final set selected by the algorithm after termination of
the first while loop, and let $\mathcal{X}$ be the sets returned at the end of
the first while loop. Since the while condition terminates when
$\alpha(\mathcal{A})\geqslant d$, we know that $\alpha(\mathcal{X})\geqslant
d$; since set $l$ was added to $\mathcal{X}$, it must be the case that before
$l$ was added, the total value of the set of items was less than $d$, so that
$\alpha(\mathcal{X}-\\{l\\})<d$. Following the standard primal-dual analysis,
we know that

$\sum_{i\in\mathcal{X}}w(i)=\sum_{i\in\mathcal{X}}\sum_{\mathcal{A}\subseteq\mathcal{F}:i\notin\mathcal{A}}\alpha^{\mathcal{A}}(i)y_{\mathcal{A}}.$
(3)

Reversing the double sum, we have that

$\sum_{i\in\mathcal{X}}\sum_{\mathcal{A}\subseteq\mathcal{F}:i\notin\mathcal{A}}\alpha^{\mathcal{A}}(i)y_{\mathcal{A}}=\sum_{\mathcal{A}\subseteq\mathcal{F}}y_{\mathcal{A}}\sum_{i\in\mathcal{X}-\mathcal{A}}\alpha^{\mathcal{A}}(i).$
(4)

Note that in any iteration of the algorithm except the last one, adding the
next set $i$ to the current sets in $\mathcal{A}$ did not cause the value of
the knapsack to become at least $d$; that is,
$\alpha(i)<d-\alpha(\mathcal{A})=d_{\mathcal{A}}$ at that point in the
algorithm. Thus, for all sets $i\in\mathcal{A}$ except $l$,
$\alpha^{\mathcal{A}}(i)=\min(\alpha(i),d_{\mathcal{A}})=\alpha(i)$, for the
point in the algorithm at which $\mathcal{A}$ was the current set of sets.
Thus, we can rewrite

$\sum_{i\in\mathcal{X}-\mathcal{A}}\alpha^{\mathcal{A}}(i)=\alpha^{\mathcal{A}}(l)+\sum_{i\in\mathcal{X}-\mathcal{A}:i\neq
l}\alpha^{\mathcal{A}}(i)=\alpha^{\mathcal{A}}(l)+\alpha(\mathcal{X}-\\{l\\})-\alpha(\mathcal{A}).$
(5)

Note that $\alpha^{\mathcal{A}}(l)\leqslant d_{\mathcal{A}}$ by definition,
and as argued at the beginning of the proof $\alpha(\mathcal{X}-\\{l\\})<d$ so
that
$\alpha(\mathcal{X}-\\{l\\})-\alpha(\mathcal{A})<d-\alpha(\mathcal{A}))=d_{\mathcal{A}}$;
thus, we have that

$\alpha^{\mathcal{A}}(l)+\alpha(\mathcal{X}-\\{l\\})-\alpha(\mathcal{A})<2d_{\mathcal{A}}.$
(6)

Therefore,

$\sum_{i\in\mathcal{X}}w(i)=\sum_{\mathcal{A}\subseteq\mathcal{F}}y_{\mathcal{A}}\sum_{i\in\mathcal{X}-\mathcal{A}}\alpha^{\mathcal{A}}(i)<2\sum_{A:A\subseteq\mathcal{F}}d_{\mathcal{A}}y_{\mathcal{A}}\leqslant
2\text{OPT},$ (7)

where the final inequality follows by weak duality since
$\sum_{A:A\subseteq\mathcal{F}}d_{\mathcal{A}}y_{\mathcal{A}}+\sum_{j\in[n]}y_{j}$
is the dual objective function.

Note that our algorithm also returns
$\sum_{i\in\mathcal{A}^{\prime}-\mathcal{X}}w(i)x_{i}$. It is interesting to
see that our algorithm picks $\mathcal{A}^{\prime}-\mathcal{X}$ sets only when
$\mathcal{X}$ does not constitute a valid set cover. Therefore, given
$\mathcal{X}$ our original problem now reduces to find only a valid set cover
as the desired value is already met by $\mathcal{X}$.

We know that the primal dual algorithm for the Set Cover problem is a $f$
factor approximation algorithm where $f$ is the frequency of the most frequent
element, see [30].

Therefore, from Equation 7, we have

$\displaystyle ALG$ $\displaystyle=\sum_{i\in\mathcal{A}^{\prime}}w(i)x_{i}$
(8)
$\displaystyle=\sum_{i\in\mathcal{X}}w(i)x_{i}+\sum_{i\in\mathcal{A}^{\prime}-\mathcal{X}}w(i)x_{i}$
(9) $\displaystyle\leqslant 2\sum_{A:A\subseteq
I}d_{\mathcal{A}}y_{\mathcal{A}}+f\sum_{j\in[n]}y_{j}$ (10)
$\displaystyle\leqslant f(\sum_{A:A\subseteq
I}d_{\mathcal{A}}y_{\mathcal{A}}+\sum_{j\in[n]}y_{j})$ (11)
$\displaystyle=f\text{OPT}$ (12)

######  Corollary 4.11.

Similar to Theorem 4.9, we obtain a d-factor approximation algorithm for the
d-Hitting Set Knapsack with target value problem.

There exists a $H_{g}$\- approximation algorithm for the Set Cover problem
[30]. We now present an alternative approximation algorithm that returns a
$H_{g}$ factor solution for the Set Cover problem, where $g$ is the size of
the maximum sized subset using the dual fitting analysis.

Algorithm 2 A max(2, $H_{g}$)-algorithm for Set Cover Knapsack with target
value problem

1:$y\leftarrow 0$

2:$\mathcal{A}\leftarrow\emptyset$

3:while $\alpha(\mathcal{A})<d$ do

4: Increase $y_{\mathcal{A}}$ until for some
$i\in\mathcal{F}-\mathcal{A},\sum_{\mathcal{B}\subseteq\mathcal{F}:i\not\in\mathcal{B}}\alpha^{\mathcal{B}}(i)y_{\mathcal{B}}\leqslant
w(i)$

5: $\mathcal{A}\leftarrow\mathcal{A}\cup\\{i\\}$

6:end while

7:$\mathcal{X}\leftarrow\mathcal{A}$

8:$\mathcal{U}^{\prime}\leftarrow\mathcal{U}-\bigcup_{i\in\mathcal{X}}\SS_{i}$

9:$\mathcal{F}^{\prime}\leftarrow\mathcal{F}-\mathcal{X}$

10:$I\leftarrow\emptyset$

11:$\hat{S}_{i}\leftarrow S_{i}$ for all $i\in\mathcal{F}^{\prime}$

12:while $I$ is not a set cover for $\mathcal{U}^{\prime}$ do

13: $l\leftarrow\text{arg
min}_{i:\hat{S}_{i}\neq\emptyset}\frac{w(i)}{|\hat{S}_{i}|}$

14: $I\leftarrow I\cup\\{l\\}$

15: $\hat{S}_{i}\leftarrow\hat{S}_{i}-S_{l}$ for all
$i\in\mathcal{F}^{\prime}$

16:end while

17:return $\mathcal{X}\cup\mathcal{I}$

######  Theorem 4.12.

Algorithm 2 returns a solution indexed by $\mathcal{X}\cup\mathcal{I}$ such
that

$\sum_{i\in\mathcal{X}\cup\mathcal{I}}w(i)\leqslant\text{max}(2,H_{g})\cdot\text{OPT}.$

######  Proof 4.13.

To prove the theorem, we construct an infeasible dual solution $y$ such that

$\sum_{i\in\mathcal{I}}w_{i}=\sum_{j=1}^{n}y_{j}.$ (13)

We will then show that $y^{\prime}=\frac{1}{H_{g}}y$ is a feasible dual
solution. By the weak duality theorem,

$\sum_{i=j}^{n}y^{\prime}_{j}\leqslant\text{LP OPT},$ (14)

so that

$\sum_{i\in\mathcal{I}}w_{i}=\sum_{j=1}^{n}y_{j}=H_{g}\sum_{j=1}^{n}y^{\prime}_{j}\leqslant
H_{g}\cdot\text{OPT}.$ (15)

In order to construct the infeasible dual solution $y$, suppose we choose to
add subset $\SS_{i}$ to our solution in iteration $k$. Then for each
$e_{j}\in\hat{\SS}_{i}$, we set $y_{j}=\frac{w(i)}{|\hat{\SS}_{i}|}$. Since
each $e_{j}\in\hat{\SS}_{i}$ is uncovered in iteration $k$, and is then
covered for the remaining iterations of the algorithm (because we added subset
$\SS_{i}$ to the solution), the dual variable $y_{j}$ is set to a value
exactly once; in particular, it is set in the iteration in which element
$e_{j}$ is covered. Furthermore,

$w(i)=\sum_{i:e_{j}\in\hat{\SS}_{i}}y_{j}$ (16)

i,e, the weight of the subset $\SS_{i}$ chosen in the $k$-th iteration is
equal to the sum of the duals $y_{j}$ of the uncovered elements that are
covered in the $k$-th iteration. This immediately implies that

$\sum_{j\in\mathcal{I}}w(i)=\sum_{i=1}^{n}y_{j}.$ (17)

It remains to prove that the dual solution $y^{\prime}=\frac{1}{H_{g}}y$ is
feasible. We must show that for each subset $\SS_{i}$,

$\sum_{i:e_{j}\in\SS_{i}}y^{\prime}_{j}\leqslant w(i).$ (18)

Pick an arbitrary subset $\SS_{i}$. Let $a_{k}$ be the number of elements in
this subset that are still uncovered at the beginning of the $k$-th iteration,
so that $a_{1}=|\SS_{i}|$, and $a_{l+1}=0$. Let $A_{k}$ be the uncovered
elements of $\SS_{i}$ covered in the $k$-th iteration, so that
$|A_{k}|=a_{k}-a_{k+1}$. If subset $\SS_{p}$ is chosen in the $k$-th
iteration, then for each element $e_{j}\in A_{k}$ covered in the $k$-th
iteration,

$y^{\prime}_{j}=\frac{w_{p}}{H_{g}|\hat{\SS}_{p}|}\leqslant\frac{w(i)}{H_{g}a_{k}},$
(19)

where $\hat{\SS}_{p}$ is the set of uncovered elements of $\SS_{p}$ at the
beginning of the $k$-th iteration. The inequality follows because if $S_{p}$
is chosen in the $k$-th iteration, it must minimize the ratio of its weight to
the number of uncovered elements it contains. Thus,

$\displaystyle\sum_{i:e_{j}\in\SS_{i}}y^{\prime}_{j}$
$\displaystyle=\sum_{k=1}^{l}\sum_{i:e_{j}\in A_{k}}y^{\prime}_{j}$
$\displaystyle\leqslant\sum_{k=1}^{l}(a_{k}-a_{k+1})\frac{w(i)}{H_{g}a_{k}}$
$\displaystyle\leqslant\frac{w(i)}{H_{g}}\sum_{k=1}^{l}\frac{a_{k}-a_{k+1}}{a_{k}}$
$\displaystyle\leqslant\frac{w(i)}{H_{g}}\sum_{k=1}^{l}\left(\frac{1}{a_{k}}+\frac{1}{a_{k}-1}+\cdots+\frac{1}{a_{k+1}+1}\right)$
$\displaystyle\leqslant\frac{w(i)}{H_{g}}\sum_{i=1}^{|\SS_{i}|}\frac{1}{i}$
$\displaystyle=\frac{w(i)}{H_{g}}H_{|\SS_{i}|}$ $\displaystyle\leqslant w(i),$

where the final inequality follows because $|\SS_{i}|\leqslant g$.

Now we know,

$\displaystyle ALG$
$\displaystyle=\sum_{i\in\mathcal{X}}w(i)x_{i}+\sum_{i\in\mathcal{I}}w(i)x_{i}$
(20)

From Equation 7, we know that $\sum_{i\in\mathcal{X}}w(i)x_{i}$ is at most
$2\leqslant 2OPT$. Also, from Equation 15, we have
$\sum_{i\in\mathcal{I}}w(i)x_{i}$ is at most $H_{g}$. Therefore,

$\displaystyle ALG$
$\displaystyle=\sum_{i\in\mathcal{X}}w(i)x_{i}+\sum_{i\in\mathcal{I}}w(i)x_{i}$
(21) $\displaystyle\leqslant
2\sum_{A:A\subseteq\mathcal{F}}d_{\mathcal{A}}y_{\mathcal{A}}+H_{g}\sum_{j\in[n]}y_{j}$
(22)
$\displaystyle=\text{max}(2,H_{g})(\sum_{A:A\subseteq\mathcal{F}}d_{\mathcal{A}}y_{\mathcal{A}}+\sum_{j\in[n]}y_{j})$
(23) $\displaystyle=\text{max}(2,H_{g})\text{OPT}$ (24)

We obtain the following corollary from Theorem 4.9.

Since Vertex Cover Knapsack is a special case of the Set Cover Knapsack
problem it follows that:

######  Corollary 4.14.

There is a 2-approximation algorithm for the Vertex Cover Knapsack with target
value problem.

However, surprisingly the same cannot be said about the Set Cover Knapsack
with budgeted weight problem. Interestingly, Set Cover Knapsack with budgeted
weight problems turns out to be hard to approximate.

######  Theorem 4.15.

For any $\rho>1$, there does not exist a $\rho$-approximation algorithm for
the Set Cover Knapsack with budgeted weight problem, unless $P=NP$.

######  Proof 4.16.

Suppose there exists a $\rho$-approximation algorithm for Set Cover Knapsack
with budgeted weight problem. We consider the Vertex Cover problem, which is
$\mathsf{NP}$-complete. In the Vertex Cover problem, we are given a graph
$\mathcal{G}$ ($\mathcal{V}$, $\mathcal{E}$) and an integer $k$, and we must
decide if there exists a subset $\mathcal{V}^{\prime}\subseteq\mathcal{V}$ of
size at most $k$ such that each edge $e\in\mathcal{E}$ is covered by at least
one vertex in $\mathcal{V}^{\prime}$. Given an instance of the Vertex Cover
problem, we can define an instance of the Set Cover Knapsack with budgeted
weight problem by setting the universe of elements to be the set of edges,
$\mathcal{U}=\\{e_{1},e_{2},\dots,e_{n}\\},\forall e_{j}\in\mathcal{E}$, the
family of subsets to be the vertices that contain the edges that are incident
to the corresponding vertices,
$\mathcal{F}=\\{v_{1},v_{2},\dots,v_{n}\\},\forall v_{i}\in\mathcal{V}$, where
each $v_{i}=\\{e_{j}\in\mathcal{E}:e_{j}\text{ is incident on }v_{i}\\}$. We
set the weight and value of each $v_{i}$ to be 1 $\forall
v_{i}\in\mathcal{F}$: there exists a vertex cover of size $k$ if and only if
the optimal value for this Set Cover Knapsack with budgeted weight instance is
$k$. Furthermore, any $\rho$ approximation algorithm must always produce a
solution $\leqslant\rho k$ if such a solution exists. Therefore, we can answer
the decision version of the Vertex Cover problem in polynomial time
contradicting the assumption that $P\neq NP$.

Similar results hold for the dual problem:

######  Corollary 4.17.

For any $\rho>1$, there does not exist a $\rho$-approximation algorithm for
the d-Hitting Set Knapsack with budgeted weight problem, unless $P=NP$.

It is easy to see that vertex cover is a 2-HITTING SET problem and follows
that:

######  Corollary 4.18.

For any $\rho>1$, there does not exist a $\rho$-approximation algorithm for
the Vertex Cover Knapsack with budgeted weight problem, unless $P=NP$.

At this point, we revisit the Minimal Vertex Cover Knapsack problem.
Interestingly, it turns out that both the versions: target value and budgeted
weight are hard to approximate. To see this, let us first consider the Minimal
Vertex Cover Knapsack problem with target value. Consider the value and weight
associated with each vertex to be 1 and set the the target value $d=k$.
Solving this problem is equivalent to answer the question if there exists a
Minimum Vertex Cover Knapsack of size $k$. Thus, by adjusting the value of $k$
from 1 to $n$, we can have an answer for the minimum Vertex Cover problem in
polynomial time, contradicting the assumption $P\neq\mathsf{NP}$. Similar to
Theorem 4.15, Minimal Vertex Cover Knapsack problem with budgeted weight is
also hard to approximate.

######  Theorem 4.19.

The Minimal Vertex Cover Knapsack problem with target value and the Minimal
Vertex Cover Knapsack problem with budgeted weight do not admit a polynomial
time $\rho$-approximation algorithm for any $\rho>1$, unless $P=\mathsf{NP}.$

However, we do not rule out the possibility of a fixed parameter tractable
(FPT) algorithm. In the next section, we give a FPT algorithm for the Minimal
Vertex Cover Knapsack problem on graphs with bounded treewidth.

##  5 Results: Parameterized Complexity

In this section, we design a dynamic programming algorithm for the Minimal
Vertex Cover Knapsack problem, parameterized by the treewidth of the input
graph. There exists $2^{\text{tw}}\cdot\text{tw}^{\mathcal{O}(1)}\cdot n$
algorithm for the Vertex Cover problem [8]. Using a similar approach we can
have dynamic programming algorithms for the Vertex Cover Knapsack and Minimum
Vertex Cover Knapsack.

######  Theorem 5.1.

There is an algorithm for Vertex Cover Knapsack with running time
$2^{\mathcal{O}(\text{tw})}\cdot n\cdot{\sf min}\\{s,d\\}$ where $n$ is the
number of vertices in the input graph, tw is the treewidth of the input graph,
$s$ is the input size of the knapsack and $d$ is the input target value.

######  Proof 5.2 (Proof Sketch).

Let $(G=(V_{G},E_{G}),{(w(u))_{u\in V_{G}},(\alpha(u))_{u\in V_{G}}},s,d)$ be
an input instance of Vertex Cover Knapsack such that $\text{tw}=tw(G)$. We
consider a nice tree decomposition
$(\mathbb{T}=(V_{\mathbb{T}},E_{\mathbb{T}}),\mathcal{X})$ of $G$ that is
rooted at a node $r$.

We define a function $\ell:V_{\mathbb{T}}\rightarrow\mathbb{N}$. For a vertex
$t\in V_{\mathbb{T}}$, $\ell(t)=\sf{dist}_{\mathbb{T}}(t,r)$, where $r$ is the
root. Note that this implies that $\ell(r)=0$. Let us assume that the values
that $\ell$ takes over the nodes of $\mathbb{T}$ is between $0$ and $L$. Now,
we describe a dynamic programming algorithm over $(\mathbb{T},\mathcal{X})$
for Vertex Cover Knapsack .

States: We maintain a DP table $D$ where a state has the following components:

  1. 1.

$t$ represents a node in $V_{\mathbb{T}}$.

  2. 2.

$\mathbb{S}$ represents a subset of the vertex subset $X_{t}$

Interpretation of States: For each node $t\in\mathbb{T}$ we keep a list
$D[t,\mathbb{S}]$ for each $\mathbb{S}\subseteq X_{t}$, holding the vertex
cover knapsack $\mathbb{S}^{\prime}$ of $G_{v}$ with $\mathbb{S}^{\prime}\cap
X_{t}=\mathbb{S}$ if such a $\mathbb{S}^{\prime}$ exist, and
$D[t,\mathbb{S}]=\infty$ otherwise.

For each state $[t,\mathbb{S}]$, we initialize $D[t,\mathbb{S}]$ to the list
$\\{(0,0)\\}$. Our computation shall be such that in the end each
$D[t,\mathbb{S}]$ stores the set of all undominated feasible pairs
$(w,\alpha)$ for the state $[t,\mathbb{S}]$.

Dynamic Programming on $D$: We describe the following procedure to update the
table $D$. We start updating the table for states with nodes $t\in
V_{\mathbb{T}}$ such that $\ell(t)=L$. When all such states are updated, then
we move to update states where the node $t$ has $\ell(t)=L-1$, and so on till
we finally update states with $r$ as the node — note that $\ell(r)=0$. For a
particular $j$, $0\leqslant j<L$ and a state $[t,\mathbb{S}]$ such that
$\ell(t)=j$, we can assume that $D[t^{\prime},\mathbb{S}^{\prime}]$ have been
evaluated for all $t^{\prime}$ such that $\ell(t^{\prime})>j$ and all subsets
$\mathbb{S}^{\prime}$ of $X_{t^{\prime}}$. Now we consider several cases by
which $D[t,\mathbb{S}]$ is updated based on the nature of $t$ in $\mathbb{T}$:

  1. 1.

Suppose $t$ is a leaf node with $X_{t}=\\{v\\}$ . Then $D[t,\\{v\\}]$ =
$(w(v),\alpha(v))$ and $D[t,\phi]$ stores the pair $(0,0)$.

  2. 2.

Suppose $t$ is an introduce node. Then it has an only child $t^{\prime}$ where
$X_{t^{\prime}}\subset X_{t}$ and there is exactly one vertex $v$ that belongs
to $X_{t}$ but not $X_{t^{\prime}}$. Then for all $\mathbb{S}\subseteq X_{t}$:
First, suppose $\mathbb{S}$ is not a vertex cover of $G[X_{t}]$, we set
$D[t,\mathbb{S}]=\infty$.
Next, suppose $v\in\mathbb{S}$. Then for each pair $(w,\alpha)$ in
$D[t^{\prime},\mathbb{S}\setminus\\{v\\}]$, if $w+w(u)\leqslant s$ we add
$(w+w(v),\alpha+\alpha(v))$ to the set in $D[t,\mathbb{S}]$. Otherwise we copy
all pairs of $D[t^{\prime},\mathbb{S}]$ to $D[t,\mathbb{S}]$.

  3. 3.

Suppose $t$ is a forget vertex node. Then it has an only child $t^{\prime}$
where $X_{t}\subset X_{t^{\prime}}$ and there is exactly one vertex $v$ that
belongs to $X_{t^{\prime}}$ but not to $X_{t}$. Then for all
$\mathbb{S}\subseteq X_{t}$, we copy all feasible undominated pairs stored in
$D[t^{\prime},\mathbb{S}]$ to $D[t,\mathbb{S}]$. If any pair stored in
$D[t,\mathbb{S}]$ is dominated by any pair of
$D[t^{\prime},\mathbb{S}\cup\\{v\\}]$, we copy only the undominated pairs to
$D[t,\mathbb{S}]$.

  4. 4.

Suppose $t$ is a join node. Then it has two children $t_{1},t_{2}$ such that
$X_{t}=X_{t_{1}}=X_{t_{2}}$. Then for all $\mathbb{S}\subseteq X_{t}$, let
$(w_{\mathbb{S}},\alpha_{\mathbb{S}})$ be the total weight and value of the
vertices in $\mathbb{S}$. Consider a pair $(w_{1},\alpha_{1})$ in
$D[t_{1},\mathbb{S}]$ and a pair $(w_{2},\alpha_{2})$ in
$D[t_{2},\mathbb{S}]$. Suppose $w_{1}+w_{2}-w_{\mathbb{S}}\leqslant s$. Then
we add
$(w_{1}+w_{2}-w_{\mathbb{S}},\alpha_{1}+\alpha_{2}-\alpha_{\mathbb{S}})$ to
$D[t,\mathbb{S}]$.

Finally, in the last step of updating $D[t,\mathbb{S}]$, we go through the
list saved in $D[t,\mathbb{S}]$ and only keep undominated pairs.

Running time: There are $n$ choices for the fixed vertex $v$. Upon fixing $v$
and adding it to each bag of $(\mathbb{T},\mathcal{X})$ we consider the total
possible number of states. Observe that the number of subproblems is small:
for every node $t$, we have only $2^{|X_{t}|}$ choices of $S$. Also, we do not
need to remember $\mathbb{S}$ explicitly; remembering the undominated and
feasible weight and profit pair will suffice. For each state, for each $w$
there can be at most one pair with $w$ as the first coordinate; similarly, for
each $\alpha$ there can be at most one pair with $\alpha$ as the second
coordinate. Thus, the number of undominated pairs in each $D[t,\mathbb{S}]$ is
at most ${\sf min}\\{s,d\\}$ time. Since the given graph $\mathcal{G}$ has a
bounded treewidth of at most $tw$, it is possible to construct a data
structure in time $tw^{\mathcal{O}(1)}\cdot n$ that allows performing
adjacency queries in time $\mathcal{O}(tw)$. For each node $t$ it takes time
$2^{tw}\cdot tw^{\mathcal{O}(1)}\cdot{\sf min}\\{s,d\\}$ to compute all the
values $D[t,\mathbb{S}]$. Since we can assume that the number of nodes of the
given tree decompositions is $\mathcal{O}(tw\cdot n)$, the total running time
of the algorithm is $2^{\mathcal{O}(\text{tw})}\cdot n\cdot{\sf min}\\{s,d\\}$
where $n$ is the number of vertices in the input graph, tw is the treewidth of
the input graph, $s$ is the input size of the knapsack and $d$ is the input
target value.

The maximum allowed value for $tw$ is $n$, as we cannot have treewidth greater
than the size of the nodes i.e $n$. With the above algorithm, we have a
pseudo-polynomial time algorithm for trees since treewidth = 1. The following
corollary holds for trees.

######  Corollary 5.3.

There is an algorithm for Vertex Cover Knapsack with Budget for trees with
complexity $\mathcal{O}(n^{2}\cdot min\\{s,(\alpha(\mathcal{V}))\\})$.

We can suitably modify the algorithm for Vertex Cover Knapsack to obtain an
algorithm for Minimum Vertex Cover Knapsack. Here we keep track of each
$i\in[n]$ i.e. we check if there exists a valid vertex cover of size $i$.
Thus, the number of states is bounded in FPT of $n$. We obtain the following
theorem:

######  Theorem 5.4.

There is an algorithm for Minimum Vertex Cover Knapsack with running time
$4^{\mathcal{O}(\text{tw})}\cdot n\cdot{\sf min}\\{s,d\\}$ where $n$ is the
number of vertices in the input graph, tw is the treewidth of the input graph,
$s$ is the input size of the knapsack and $d$ is the input target value.

Interestingly, the same standard approach does not seem to hold good for the
Minimal Vertex Cover Knapsack. This is so because in case of a join node, say
$t$, there can exist a vertex in the solution that is not redundant in either
of the subgraphs rooted at $t_{1}$ and $t_{2}$, where $t_{1}$ and $t_{2}$ are
the children of $t$, but it becomes redundant for the subgraph rooted at $t$.
We discuss an algorithm for Minimal Vertex Cover Knapsack next.

######  Theorem 5.5.

There is an algorithm for Minimal Vertex Cover Knapsack with running time
$8^{\mathcal{O}(\text{tw})}\cdot n\cdot{\sf min}\\{s,d\\}$ where $n$ is the
number of vertices in the input graph, tw is the treewidth of the input graph,
$s$ is the input size of the knapsack and $d$ is the input target value.

######  Proof 5.6.

Let $(G=(V_{G},E_{G}),{(w(u))_{u\in V_{G}},(\alpha(u))_{u\in V_{G}}},s,d)$ be
an input instance of Minimal Vertex Cover Knapsack such that
$\text{tw}=tw(G)$. We consider a nice edge tree decomposition
$(\mathbb{T}=(V_{\mathbb{T}},E_{\mathbb{T}}),\mathcal{X})$ of $G$ that is
rooted at a node $r$.

We define a function $\ell:V_{\mathbb{T}}\rightarrow\mathbb{N}$. For a vertex
$t\in V_{\mathbb{T}}$, $\ell(t)=\sf{dist}_{\mathbb{T}}(t,r)$, where $r$ is the
root. Note that this implies that $\ell(r)=0$. Let us assume that the values
that $\ell$ takes over the nodes of $\mathbb{T}$ is between $0$ and $L$. Now,
we describe a dynamic programming algorithm over $(\mathbb{T},\mathcal{X})$
for Minimal Vertex Cover Knapsack.

States: We maintain a DP table $D$ where a state has the following components:

  1. 1.

$t$ represents a node in $V_{\mathbb{T}}$.

  2. 2.

$V_{1}$, $V_{2}$ are subsets of the bag $X_{t}$, not necessarily disjoint.

  3. 3.

$V_{1}$ represents the intersection of $X_{t}$ with the minimal vertex cover
knapsack of the subgraph $G_{t}\setminus$ the edges incident on
$V_{2}\setminus V_{1}$.

Interpretation of States: For each node $t\in\mathbb{T}$ we keep a list
$D[t,V_{1},V_{2}]$ for each $\mathbb{S}\subseteq X_{t}$, holding the minimal
vertex cover knapsack $\mathbb{S}^{\prime}$ of $G_{t}$ with
$\mathbb{S}^{\prime}\cap X_{t}=\mathbb{S}=V_{1}\cup V_{2}$, if such a
$\mathbb{S}^{\prime}$ exist, and $D[t,V_{1},V_{2}]=(\infty,\infty)$ otherwise.
For a node $t$, $V_{1}$ is the intersection of $X_{t}$ with the minimal vertex
cover knapsack of the subgraph $G_{t}\setminus$ the edges incident on
$V_{2}\setminus V_{1}$.

Genesis of the subsets $V_{1}$ and $V_{2}$: We wish to capture the information
about the minimal solution in the subgraph defined by removing the edges
incident on $V_{2}\setminus V_{1}$. Maintaining this information at every node
is essential to compute the minimal solution, especially in case of a join
node. Consider that a node $t$ is a join node i.e. it has two children $t_{1}$
and $t_{2}$ such that $X_{t}=X_{t_{1}}=X_{t_{2}}$. The nodes $t_{1}$ and
$t_{2}$ are the root nodes for the subgraphs $G_{t_{1}}$ and $G_{t_{2}}$. Here
we guess a subset of vertices $\mathbb{S}\subseteq X_{t}$. In this case, it
may so happen that all vertices in $\mathbb{S}$ might not be non-redundant. To
see this, let us consider the graph $G_{t_{1}}$ and observe how the vertices
in $\mathbb{S}$ could be redundant in $G_{t_{1}}$. Define $V_{1}^{\prime}$ as
the intersection of the minimal solution $\mathbb{S}^{\prime}$ with graph
$G_{t_{1}}\setminus X_{t_{1}}$. Similarly, call $V_{2}^{\prime}$ as the
intersection of the minimal solution $\mathbb{S}^{\prime}$ with graph
$G_{t_{2}}\setminus X_{t_{2}}$. Consider a vertex $a\in V_{1}^{\prime}$, $b\in
V_{2}$ and $c\in G_{t_{2}}\setminus(X_{t_{2}}\cup V_{2}^{\prime})$. Now it is
easy to see that the vertex $b\in V_{2}$ is redundant in the subgraph
$G_{t_{1}}$, however it is not redundant with respect to $G_{t_{2}}$. To keep
track of non redundant vertices, we require to compute the intersection of a
minimal solution in each subgraph of $G_{t_{1}}$, i.e we assume two subsets
$W_{1}$ and $W_{2}$ of $V_{1}$ and maintain $W_{1}$ in $G_{t_{1}}$ such that
it contains all non redundant vertices of the minimal solution in the subgraph
$G_{t_{1}}\setminus$ edges incident on $(W_{2}\cap V_{2})\setminus W_{1}$. In
a similar fashion, $W_{2}$ stores all the non redundant vertices of the
minimal solution in the subgraph $G_{t_{2}}\setminus$ edges incident on
$(W_{1}\cup V_{2})\setminus W_{1}$. In other words, in particular for the case
of a join node $t$, for a given pair of subsets $V_{1}$ and $V_{2}$, $V_{1}$
is the intersection of $X_{t}$ with a minimal solution. The set $V_{1}$ is
further sub divided into sets $W_{1}$ and $W_{2}$ such that $W_{1}$ stores the
non redundant vertices of the minimal solution in the graph $G_{t_{1}}$. We
find $W_{1}\subseteq V_{1}$, by checking whether the removal a vertex in
$V_{1}$, can still form a vertex cover of $G_{t_{1}}$, if so then we place
that vertex in $W_{2}$. Thus, we check for all such vertices and place only
the non redundant vertices in $W_{1}$ for the subgraph $G_{t_{1}}$.
Similarly,we compute the non redundant vertices of $G_{t_{2}}$, in $W_{2}$.
Now we can now easily compute the non redundant minimal vertex cover knapsack
entries for $D[t,V_{1},V_{2}]$ i.e.in $t_{1}$, the state $D[t_{1},W1,W2\cup
V2]$ has to be looked up and in $t_{2}$, $D[t_{2},W2,W1\cup V2]$ has to be
looked up.

For each state $D[t,V_{1},V_{2}]$, we initialize $D[t,V_{1},V_{2}]$ to the
list $\\{(0,0)\\}$. Our computation shall be such that in the end each
$D[t,V_{1},V_{2}]$ stores the set of all undominated feasible pairs
$(w,\alpha)$ for the state $[t,V_{1},V_{2}]$.

Dynamic Programming on $D$: We describe the following procedure to update the
table $D$. We start updating the table for states with nodes $t\in
V_{\mathbb{T}}$ such that $\ell(t)=L$. When all such states are updated, then
we move to update states where the node $t$ has $\ell(t)=L-1$, and so on till
we finally update states with $r$ as the node — note that $\ell(r)=0$. For a
particular $j$, $0\leqslant j<L$ and a state $[t,V_{1},V_{2}]$ such that
$\ell(t)=j$, we can assume that $D[t,V_{1},V_{2}]$ have been evaluated for all
$t^{\prime}$, such that $\ell(t^{\prime})>j$ and all subsets
$\mathbb{S}^{\prime}$ of $X_{t^{\prime}}$. Now we consider several cases by
which $D[t,V_{1},V_{2}]$ is updated based on the nature of $t$ in
$\mathbb{T}$:

  1. 1.

Suppose $t$ is a leaf node with $X_{t}=\\{v\\}$ . Then $D[t,v,\emptyset]$ =
$(w(v),\alpha(v))$, or $D[t,\emptyset,v]$ = $(0,0)$ and
$D[t,\emptyset,\emptyset]$ stores the pair $(0,0)$.

  2. 2.

Suppose $t$ is an introduce node. Then it has an only child $t^{\prime}$ where
$X_{t^{\prime}}\subset X_{t}$ and there is exactly one vertex $v$ that belongs
to $X_{t}$ but not $X_{t^{\prime}}$. Then for all $\mathbb{S}\subseteq X_{t}$:
First, suppose $\mathbb{S}$ is not a vertex cover of $G[X_{t}]$, we set
$D[t,V_{1},V_{2}]=(\infty,\infty)$.
Otherwise, we have three cases:

    1. (a)

Case 1: If $v\not\in V_{1}\cup V_{2}$, then we copy each pair $(w,\alpha)$
from $D[t^{\prime},V_{1},V_{2}]$

    2. (b)

Case 2: If $v\in V_{1}$, then

      1. i.

we check if $N(v)\setminus V_{1}\neq\emptyset$, then

        1. A.

if for each pair $(w,\alpha)$ in $D[t^{\prime},V_{1}\setminus\\{v\\},V_{2}]$,
$w+w(v)\leqslant s$, then add all such pairs $(w+w(v),\alpha+\alpha(v)$ in
$D[t^{\prime},V_{1}\setminus\\{v\\},V_{2}]$ to $D[t,V_{1},V_{2}]$.

        2. B.

otherwise copy each pair $(w,\alpha)$ from
$D[t^{\prime},V_{1}\setminus\\{v\\},V_{2}]$ to $D[t,V_{1},V_{2}]$.

      2. ii.

Otherwise we store $(\infty,\infty)$.

    3. (c)

Case 3: $v\in V_{2}$, then for each pair $(w,\alpha)$ in
$D[t^{\prime},V_{1},V_{2}\setminus\\{v\\}]$, we copy each pair of
$D[t^{\prime},V_{1},V_{2}\setminus\\{v\\}]$ to $D[t,V_{1},V_{2}]$.

  3. 3.

Suppose $t$ is a forget vertex node. Then it has an only child $t^{\prime}$
where $X_{t}\subset X_{t^{\prime}}$ and there is exactly one vertex $v$ that
belongs to $X_{t^{\prime}}$ but not to $X_{t}$. We copy each undominated
$(w,\alpha)$ pair stored in $D[t^{\prime},V_{1}\cup\\{v\\},V_{2}]$,
$D[t^{\prime},V_{1},V_{2}\cup\\{v\\}]$ and $D[t^{\prime},V_{1},V_{2}]$ to
$D[t,V_{1},V_{2}]$.

  4. 4.

Suppose $t$ is a join node. Then it has two children $t_{1},t_{2}$ such that
$X_{t}=X_{t_{1}}=X_{t_{2}}$. Let $(w(V_{1}\cap V_{2}),\alpha(V_{1}\cap
V_{2}))$ be the total weight and value of the vertices in $V_{1}\cap V_{2}$.
Then for all $W_{1},W_{2}\subseteq V_{1}\subseteq X_{t}$, consider a pair
$(w_{1},\alpha_{1})$ in $D[t_{1},W_{1},W_{2}\cup V_{2}]$ and a pair
$(w_{2},\alpha_{2})$ in $D[t_{2},W_{2},W_{1}\cup V_{2}]$. Suppose
$w_{1}+w_{2}-w(V_{1}\cap V_{2})\leqslant s$. Then we add
($w_{1}+w_{2}-w(V_{1}\cap V_{2}),\alpha_{1}+\alpha_{2}-\alpha(V_{1}\cap
V_{2})$) to $D[t,V_{1},V_{2}]$.

Finally, in the last step of updating $D[t,V_{1},V_{2}]$, we go through the
list saved in $D[t,V_{1},V_{2}]$ and only keep undominated pairs.

Correctness of the algorithm: We demonstrate the correctness of our algorithm
by analyzing each case.

In each state we maintain the invariant $V_{1},V_{2}\subseteq X_{t}$ such that
$V_{1}=X_{t}\cap$ minimal vertex cover knapsack of $G_{t}\setminus$ edges
incident on $V_{2}\setminus V_{1}$. By definition,

  1. 1.

Leaf node: Recall that in our modified nice tree decomposition we have added a
vertex $v$ to all the bags. Suppose a leaf node contains a single vertex $v$,
$D[L,v,\emptyset]=(w(v),\alpha(v))$, $D[L,\emptyset,v]=(0,0)$ and
$D[L,\emptyset,\emptyset]$ stores the pair $(0,0)$. This is true in particular
when $i=L$, the base case. From now we can assume that for a node $t$ with
$\ell(t)=j<L$ all $D[t^{\prime},V_{1},V_{2}]$ entries are correct and
correspond to minimal vertex cover in $G_{t^{\prime}}$ when
$\ell(t^{\prime})>j$.

  2. 2.

Introduce node: When $t$ is an introduce node, there is a child $t^{\prime}$.
We are introducing a vertex $v$ and the edges associated with it $G_{t}$.
Since $\ell(t^{\prime})>\ell(t)$, by induction hypothesis all entries in
$D[t^{\prime},V_{1}\setminus\\{v\\},V_{2}]$ and
$D[t^{\prime},V_{1},V_{2}\setminus\\{v\\}]$, $\forall$
$V_{1}\setminus\\{v\\},V_{2}\setminus\\{v\\}\subseteq X_{t^{\prime}}$ are
already computed. We update pairs in $D[t,V_{1},V_{2}]$ from
$D[t^{\prime},V_{1}\setminus\\{v\\},V_{2}]$ and
$D[t^{\prime},V_{1},V_{2}\setminus\\{v\\}]$ such that either $v$ is considered
as part of a minimal solution or not.

  3. 3.

Forget node: When $t$ is a forget node, there is a child $t^{\prime}$. We are
forgetting a vertex $v$ and the edges associated with it $G_{t}$. Since
$\ell(t^{\prime})>\ell(t)$, by induction hypothesis all entries in
$D[t^{\prime},V_{1}\cup\\{v\\},V_{2}]$,
$D[t^{\prime},V_{1},V_{2}\cup\\{v\\}]$, and $D[t^{\prime},V_{1},V_{2}]$,
$\forall$ $V_{1},V_{2},V_{1}\cup\\{v\\},V_{2}\cup\\{v\\}\subseteq
X_{t^{\prime}}$ are already computed. We copy each undominated $(w,\alpha)$
pair stored in $D[t^{\prime},V_{1}\cup\\{v\\},V_{2}]$,
$D[t^{\prime},V_{1},V_{2}\cup\\{v\\}]$ and $D[t^{\prime},V_{1},V_{2}]$ to
$D[t,V_{1},V_{2}]$.

  4. 4.

Join node: When $t$ is a forget node, there are two children $t_{1}$ and
$t_{2}$ of $t$, such that $X_{t}=X_{t_{1}}=X_{t_{2}}$. For all subsets
$V_{1}\subseteq X_{t}$ we partition $V_{1}$ into two subsets $W_{1}$ and
$W_{2}$ (not necessarily disjoint) such that $W_{1}$ is the intersection of
$X_{t_{1}}$ with minimal solution in the graph $G_{t_{1}}\setminus$ edges
incident on $(W_{2}\cup V_{2})\setminus W_{1}$. Similarly, $W_{2}$ is the
intersection of $X_{t_{2}}$ with minimal solution in the graph
$G_{t_{2}}\setminus$ edges incident on $(W_{1}\cup V_{2})\setminus W_{2}$. By
the induction hypothesis, the computed entries in $D[t_{1},W_{1},W_{2}\cup
V_{2}]$ and $D[t_{2},W_{2},W_{1}\cup V_{2}]$ where $W_{1}\cup W_{2}=V_{1}$ are
correct and store the non redundant minimal vertex cover for the subgraph
$G_{t_{1}}$ in $W_{1}$ and similarly, $W_{2}$ for $G_{t_{2}}$. Now we add
($w_{1}+w_{2}-w(V_{1}\cap V_{2}),\alpha_{1}+\alpha_{2}-\alpha\\{V_{1}\cap
V_{2}))$) to $D[t,V_{1},V_{2}]$.

Running Time: There are $n$ choices for the fixed vertex $v$. Upon fixing $v$
and adding it to each bag of $(\mathbb{T},\mathcal{X})$ we consider the total
possible number of states. Observe that the number of subproblems is small:
for every node $t$, we have only $2^{|X_{t}|}$ choices of $S$, $2^{|S|}$
choices for $V_{1}$ and $2^{|V_{1}|}$ choices for $W_{1}$ i,e,
$\mathcal{O}(8^{|X_{t}|})$. Also, we do not need to remember $\mathbb{S}$
explicitly; remembering the undominated and feasible weight and profit pair
will suffice. Therefore, are at most $\mathcal{O}(n)\cdot 8^{\text{tw}+1}$
states. For each state, since we are keeping only undominated pairs, for each
$w$ there can be at most one pair with $w$ as the first coordinate; similarly,
for each $\alpha$ there can be at most one pair with $\alpha$ as the second
coordinate. Thus, the number of undominated pairs in each $D[t,V_{1},V_{2}]$
is at most ${\sf min}\\{s,d\\}$. By the description of the algorithm, the
maximum length of the list stored at $D[t,V_{1},V_{2}]$ during updation, but
before the check is made for only undominated pairs, is
$8^{\text{tw}+1}\cdot{\sf min}\\{s,d\\}$. Thus, updating the DP table at any
vertex takes $8^{\text{tw}+1}\cdot{\sf min}\\{s,d\\}$ time. Since there are
$\mathcal{O}(n\cdot\text{tw})$ vertices in $\mathbb{T}$, the total running
time of the algorithm is $8^{\mathcal{O}(\text{tw})}\cdot n\cdot{\sf
min}\\{s,d\\}$.

The treewidth of a tree is 1. This implies the following corollary:

######  Corollary 5.7.

There exists an algorithm for Vertex Cover Knapsack for trees running in time
$\mathcal{O}(n\cdot{\sf min}\\{s,d\\})$.

The above corollary also implies that Vertex Cover Knapsack for trees is
pseudo polynomial.

##  6 Conclusion

We study the classical Knapsack problem with the graph theoretic constraints,
namely vertex cover and its interesting variants like Minimum Vertex Cover
Knapsack, Minimal Vertex Cover Knapsack and Vertex Cover Knapsack with Budget
for both general graphs and trees. We show that the Vertex Cover Knapsack is
strongly $\mathsf{NP}$-complete and show the computational complexity of the
other variants. We also discuss the generalized version of the problem i.e.
Set Cover Knapsack and d-Hitting Set. Our results show the existence of a
2-factor approximation algorithm for Vertex Cover Knapsack with target value
and the unlikeliness of a $\rho$-factor algorithm for Vertex Cover Knapsack
with budgeted weight. Parameterized by the treewidth of a given graph, we also
prove that all the variants admit FPT algorithms.

## References

  * [1] Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, and Marco Protasi.  Complexity and approximation: Combinatorial optimization problems and their approximability properties.  Springer Science & Business Media, 2012.
  * [2] R Balasubramanian, Michael R Fellows, and Venkatesh Raman.  An improved fixed-parameter algorithm for vertex cover.  Information Processing Letters, 65(3):163–168, 1998.
  * [3] Reuven Bar-Yehuda and Shimon Even.  A linear-time approximation algorithm for the weighted vertex cover problem.  Journal of Algorithms, 2(2):198–203, 1981.
  * [4] Reuven Bar-Yehuda and Shimon Even.  A local-ratio theorem for approximating the weighted vertex cover problem.  In North-Holland Mathematics Studies, volume 109, pages 27–45. Elsevier, 1985.
  * [5] Nicolas Boria, Federico Della Croce, and Vangelis Th Paschos.  On the max min vertex cover problem.  Discrete Applied Mathematics, 196:62–71, 2015.
  * [6] Norbert Bus, Nabil H Mustafa, and Saurabh Ray.  Practical and efficient algorithms for the geometric hitting set problem.  Discrete Applied Mathematics, 240:25–32, 2018.
  * [7] Miroslav Chlebík and Janka Chlebíková.  Crown reductions for the minimum weighted vertex cover problem.  Discrete Applied Mathematics, 156(3):292–312, 2008.
  * [8] Marek Cygan, Fedor V Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.  Parameterized algorithms, volume 5.  Springer, 2015.
  * [9] Peter Damaschke.  Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover.  Discrete Optimization, 8(1):18–24, 2011.
  * [10] François Delbot and Christian Laforest.  Analytical and experimental comparison of six algorithms for the vertex cover problem.  Journal of Experimental Algorithmics (JEA), 15:1–1, 2010.
  * [11] Rodney G Downey, Michael R Fellows, and Ulrike Stege.  Parameterized complexity: A framework for systematically confronting computational intractability.  Contemporary Trends in Discrete Mathematics, 49:49–99, 1997.
  * [12] Rodney G Downey and Michael Ralph Fellows.  Parameterized complexity.  Springer Science & Business Media, 2012.
  * [13] Stephane Durocher and Robert Fraser.  Duality for geometric set cover and geometric hitting set problems on pseudodisks.  In CCCG, 2015.
  * [14] Bruno Escoffier, Laurent Gourvès, and Jérôme Monnot.  Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs.  Journal of Discrete Algorithms, 8(1):36–49, 2010.
  * [15] MR Fellows and U Stege.  An improved fixed-parameter-tractable algorithm for vertex cover.  Relatório técnico, Department of Computer Science, ETH Zurich, 1999.
  * [16] Henning Fernau.  Parameterized algorithmics: A graph-theoretic approach.  PhD thesis, Citeseer, 2005.
  * [17] Fedor V Fomin, Serge Gaspers, and Saket Saurabh.  Branching and treewidth based exact algorithms.  In Algorithms and Computation: 17th International Symposium, ISAAC 2006, Kolkata, India, December 18-20, 2006. Proceedings 17, pages 16–25. Springer, 2006.
  * [18] Toshihiro Fujito and Tomoya Nakamura.  Eternal connected vertex cover problem.  In Theory and Applications of Models of Computation: 16th International Conference, TAMC 2020, Changsha, China, October 18–20, 2020, Proceedings 16, pages 181–192. Springer, 2020.
  * [19] Michael R Garey and David S. Johnson.  The rectilinear steiner tree problem is np-complete.  SIAM Journal on Applied Mathematics, 32(4):826–834, 1977.
  * [20] Michael R Garey and David S Johnson.  Computers and intractability.  A Guide to the, 1979.
  * [21] David G. Harris and N. S. Narayanaswamy.  A faster algorithm for vertex cover parameterized by solution size.  In Olaf Beyersdorff, Mamadou Moustapha Kanté, Orna Kupferman, and Daniel Lokshtanov, editors, 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024, March 12-14, 2024, Clermont-Ferrand, France, volume 289 of LIPIcs, pages 40:1–40:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.  URL: https://doi.org/10.4230/LIPIcs.STACS.2024.40, doi:10.4230/LIPICS.STACS.2024.40.
  * [22] Yuchao Li, Wei Wang, and Zishen Yang.  The connected vertex cover problem in k-regular graphs.  Journal of Combinatorial Optimization, 38:635–645, 2019.
  * [23] Burkhard Monien and Ewald Speckenmeyer.  Ramsey numbers and an approximation algorithm for the vertex cover problem.  Acta Informatica, 22:115–123, 1985.
  * [24] Rolf Niedermeier and Peter Rossmanith.  Upper bounds for vertex cover further improved.  In STACS 99: 16th Annual Symposium on Theoretical Aspects of Computer Science Trier, Germany, March 4–6, 1999 Proceedings 16, pages 561–570. Springer, 1999.
  * [25] Rolf Niedermeier and Peter Rossmanith.  On efficient fixed-parameter algorithms for weighted vertex cover.  Journal of Algorithms, 47(2):63–77, 2003.
  * [26] Kaustav Paul and Arti Pandey.  Eternal connected vertex cover problem in graphs: Complexity and algorithms.  In Conference on Algorithms and Discrete Applied Mathematics, pages 179–193. Springer, 2024.
  * [27] Steven S. Skiena.  Set and String Problems, pages 620–656.  Springer London, London, 2008.  doi:10.1007/978-1-84800-070-4_18.
  * [28] Ulrike Stege and Michael Ralph Fellows.  An improved fixed parameter tractable algorithm for vertex cover.  Technical report/Departement Informatik, ETH Zürich, 318, 1999\.
  * [29] Vijay V Vazirani.  Approximation algorithms, volume 1.  Springer, 2001.
  * [30] David P Williamson and David B Shmoys.  The design of approximation algorithms.  Cambridge university press, 2011.