The set cover problem

Let a finite set \(U\) of \(n\) elements be given, together with a collection of its subsets \(\mathcal{S}=\left\{ S_{1}, \ldots , S_{k}\right\} \subset 2^U\). In particular, if \(\left|S_i\right| = 2, \; \forall i\), then \((U, \mathcal{S})\) is an undirected graph. A sub-collection \(\mathcal{S}^{\prime } \subseteq \mathcal{S}\) is called a cover if every element of \(U\) belongs to at least one member of \(\mathcal{S}^{\prime }\), i.e.,

\[ \bigcup _{S \in \mathcal{S}'}S = U \]

Minimum-cardinality set cover

A finite set \(U\) of \(n\) elements, a collection of its subsets \(\mathcal{S} \subset 2^U\).

A cover from \(\mathcal{S}\) of minimum cardinality.

The minimum-cardinality set cover problem

A universe \(U\) of 9 elements and a family \(\mathcal S=\{S_1,\dots,S_6\}\) of overlapping subsets. Hover over a set's label to highlight it and see its elements; hover over a point to see which sets it belongs to.

A generalization of this problem is the minimum-weight set cover problem. This is the version we will study.

Minimum-weight set cover

A finite set \(U\) of \(n\) elements, a collection of its subsets \(\mathcal{S} \subset 2^U\), and weights on the subsets \(c: \mathcal{S} \rightarrow \mathbf{Q}^{+}\).

A sub-collection of \(\mathcal{S}\) of minimum weight that covers the set \(U\).

The minimum-weight set cover problem

The same configuration \(U,\mathcal S\), but each set \(S_i\) now carries a weight \(c(S_i)\) (the number below its label). Hover over a set's label to highlight it.

1 A greedy algorithm for the set cover problem

In 1979 the Czech mathematician Václav Chvátal proposed a greedy algorithm for the set cover problem.

Algorithm 1 Chvátal’s greedy algorithm for the set cover problem (\(U, S, c: S \rightarrow Q^{+}\))

• \(C \gets \varnothing\) (the set of elements of \(U\) already covered)
• \(\operatorname{Sol} \gets \varnothing\) (the set of chosen subsets from \(S\))
• while \(C \neq U\) do
  • Choose a set \(S_{i} \in S \setminus \operatorname{Sol}\) minimizing \[ \alpha_{i} = \frac{c(S_i)}{|S_i \setminus C|} \] (cost per unit of not-yet-covered element)
  • for each \(u \in S_i \setminus C\) do
    • \(\operatorname{price}(u) \gets \frac{c(S_i)}{|S_i \setminus C|}\) (assign a price to each newly covered element)
  • \(C \gets C \cup S_i\) (update the set of covered elements)
  • \(\operatorname{Sol} \gets \operatorname{Sol} \cup \{S_i\}\) (add the chosen set to the solution)
• return \(\operatorname{Sol}\)

At each iteration we choose the most efficient set, remove the covered elements, and continue until every element is covered. Let \(C\) be the set of elements already covered in previous iterations. For each set \(S_{i}\) define its efficiency as \(\alpha_{i}=\frac{c\left(S_{i}\right)}{\left|S_{i} \setminus C\right|}\). The efficiency of a set equals the average cost at which the elements of that set not yet covered in previous iterations get covered. Call the price of an element the average cost at which it was covered. All newly covered elements of the set \(S_{i}\) receive the same price.

Lemma 1 Let \(S \in \mathcal{S}\) be an arbitrary subset. Number the elements of \(S\) in the order in which they were covered (“bought”) by the greedy algorithm: \(u_1, u_2, \ldots , u_l \in S\). Then \[ \operatorname {price}(u_j) \leq \frac{c(S)}{l-j+1}, \qquad j \in \left\{ 1, \ldots , l\right\} \]

Mn-proofProof

Consider the iteration at which the element \(u_j\) was covered.

• By this iteration, at most \(j-1\) elements of \(S\) have been covered;

• At least \(l - (j-1)\) elements of \(S\) remain uncovered;

• Hence, had the algorithm chosen the set \(S\) itself into \(\operatorname {Sol}\) at this iteration, its efficiency would have been at most \(\frac{c(S)}{l-(j-1)}\);

• Since the algorithm chooses the set of minimal efficiency, the assigned price is no larger: \(\operatorname {price}(u_j) \leq \frac{c(S)}{l-j+1}\).

For a natural number \(n \in \mathbb {N}\) denote by

\[ H_n := 1 +\frac{1}{2}+\frac{1}{3}+\ldots +\frac{1}{n} \]

the partial sum of the harmonic series. Note that \(H_n = \ln n + \gamma + o(1)\), where \(\gamma \approx 0.577\) is the Euler–Mascheroni constant; in particular, \(\ln n < H_n \leq \ln n + 1\).

Corollary 1 For an arbitrary \(S \in \mathcal{S}\) \[ \operatorname {price}(S) = \sum _{j=1}^l \operatorname {price}(u_j) \leq c(S) \cdot H_l \] where \(l = \left|S\right|\).

Mn-proofProof

We have \[ \operatorname {price}(S) = \sum _{j=1}^l \operatorname {price}(u_j) \leq \sum _{j=1}^l \frac{c(S)}{l-(j-1)} = c(S)H_l \]

Theorem 1 Chvátal’s algorithm is an \(H_{\tilde{n}}\)-approximation algorithm for the set cover problem, where \(\tilde{n}\) is the cardinality of the largest set in \(\mathcal{S}\). In particular, it is an \(H_n\)-approximation algorithm, where \(n\) is the number of elements of \(U\).

Mn-proofProof

Let \(\sigma^* = \left\{ S_{i_1}, \ldots , S_{i_{k^*}}\right\}\) be an optimal solution. Its cost is \(\operatorname {OPT} = \sum_{m=1}^{k^*} c(S_{i_m})\). Let \(\sigma_{\operatorname {GA}}\) be the output of the greedy algorithm. We have \[ \operatorname {price}(\sigma _{\operatorname {GA}}) = \sum _{u\in U}\operatorname {price}(u) \leq \sum _{m=1}^{k^*} \operatorname {price}(S_{i_m}) \leq \sum _{m=1}^{k^*} c(S_{i_m}) \cdot H_{\left|S_{i_m}\right|} = \operatorname {OPT} \cdot H_{\tilde{n}} \]

A tight example for Chvátal's algorithm

\(n\) singleton sets with weights \(\frac1n,\frac1{n-1},\dots,1\) sit inside a single set of weight \(1+\varepsilon\) containing all elements. At every iteration the greedy algorithm takes the set with least cost per uncovered element — and this is always the next singleton: its cost \(\frac1{n-i+1}\) is slightly less than the big set's cost, \(\frac{1+\varepsilon}{n-i+1}\). Step through the iterations with the buttons, or set \(n\).

\(n=\)5

Can one obtain a better algorithm? No: the set cover problem cannot be approximated within a factor of \((1 - o(1))\ln (n)\).

2 The minimum-weight vertex cover problem

2.1 Using a set-cover algorithm

Note that the minimum-weight vertex cover problem (in particular, the minimum-cardinality version) is a special case of the set cover problem. Indeed, let a graph \(G=(V, E)\) be given, and suppose we must find a vertex cover of minimum weight. We can build the following instance of the set cover problem:

• Identify the universe \(U\) with the edge set \(E\), i.e., \(U = E\).

• Each vertex \(v \in V\) corresponds to a set \(S_v \subseteq U\) consisting of all edges incident to \(v\).

• The cost function is \(c: S_v \mapsto \text{the weight of vertex } v\).

Then any set cover \(S' \subseteq \{ S_v : v \in V\}\) covering \(U\) corresponds to a choice of vertices \(V' \subseteq V\) forming a vertex cover of the graph. Minimizing the total weight of the chosen sets \(S'\) is equivalent to minimizing the weight of the vertex cover.

Note that the greedy algorithm for the minimum-cardinality vertex cover problem is a special case of Chvátal’s algorithm. We thus obtain its accuracy bound: \(H_{\tilde{n}}\), where \(\tilde{n}\) is the maximum vertex degree in \(G\).

2.2 Constant-factor algorithms via weight splitting

In the introduction we obtained an algorithm for the minimum-cardinality vertex cover problem with a fixed accuracy bound of \(2\). Will it achieve the same accuracy for the more general problem, i.e., the minimum-weight cover problem? No!

A minimum-weight cover does not reduce to a minimum-cardinality cover

The same graph on 7 vertices: first without weights, with its minimum-cardinality cover, then with vertex weights — and a cover of smaller weight but larger cardinality. Hover over a vertex to see its weight.

2.2.1 The local ratio algorithm

The idea of the local ratio algorithm: splitting \(w=w_1+w_2\)

We choose an edge \(\{v,v'\}\) incident to the cheapest vertex and subtract \(c=\min(w(v),w(v'))\) from both of its endpoints: \(w_1\) is concentrated on these two vertices (\(c\) at each, zero elsewhere), and \(w_2=w-w_1\) is the same graph with reduced weights. Any cover of the graph \((V,E,w_1)\) is a 2-approximation: at least one of the edge's two endpoints must be covered. Hover over a vertex to track its weight across all three panels.

=

+

endpoints of the chosen edgeweight became zero

A full run of the local ratio algorithm

At each step \(i\) the algorithm takes an edge incident to the cheapest of the still-nonzero vertices and subtracts \(c\) from both of its endpoints — the weight \(t_i\) is concentrated on these two vertices. After 5 steps, the residual \(t_6\) marks the outlined vertices — this is the algorithm's solution. Hover over a vertex to see its residual weight.

=

Theorem 2 (On splitting a graph) Let a graph \((V,E)\) and a vertex weight function \(w: V \to \mathbb {R}_+\) be given, and suppose the weight function splits as a sum of functions: \(w = w_1 + w_2\). If \(V' \subset V\) is a vertex cover that is a \(\rho\)-approximation of the optimal cover both for \((V,E,w_1)\) and for \((V,E,w_2)\), then \(V'\) is also a \(\rho\)-approximation for the original vertex-weighted graph \((V,E,w)\).

Mn-proofProof

Let \(V^*\), \(V^*_1\), \(V^*_2\) be optimal covers for the graph \((V,E)\) with weight functions \(w\), \(w_1\), \(w_2\) respectively. We are given: \[ \begin{align} w_1(V') & \leq \rho w_1(V^*_1) \leq \rho w_1(V^*) \\ w_2(V') & \leq \rho w_2(V^*_2) \leq \rho w_2(V^*) \\ \end{align} \] We obtain \[ w(V') = w_1(V') + w_2(V') \leq \rho \left(w_1(V^*) + w_2(V^*)\right) = \rho w(V^*) \]

2.2.2 The level algorithm

A second way to split the weights: do it globally rather than edge by edge.

Call a function \(w: V \to \mathbb {Q}_+\) of vertex weights degree-proportional if there exists a constant \(c>0\) such that the weight of every vertex \(v \in V\) equals \(w(v) = c \cdot \operatorname {deg}(v)\).

The level algorithm: another way to split the weights

A global subtraction proportional to vertex degree: \(c=\min_v w(v)/\deg(v)=3.5\) (attained at vertex \(ML\), \(\deg=4\)), so \(w_1(v)=c\cdot\deg(v)\) for every vertex, and \(w_2=w-w_1\) is the residual function (the residual at \(ML\) equals \(0\)). Hover over a vertex to see its degree and all three weights.

=

+

w₁ = 3.5·deg — the minimum of w/degresidual 0

Lemma 2 Let \(w: V \rightarrow \mathbf{Q}^{+}\) be a degree-proportional function. Then \[ w(V) \leq 2 \operatorname {OPT} \]

Mn-proofProof

Let \(c>0\) be the constant such that \(w(v)=c \cdot \operatorname {deg}(v)\). Let \(U\) be an optimal vertex cover of the graph \(G\). Since \(U\) covers all edges, \[ \sum _{v \in U} \operatorname {deg}(v) \geq |E| \] It follows that \(w(U) \geq c|E|\). Recalling that \(\sum_{v \in V} \operatorname {deg}(v)=\) \(2|E|\), we get \(w(V)=2 c|E|\). Altogether \(w(V) = 2c\left|E\right| \leq 2 w(U) = 2\operatorname {OPT}\).

Let \(w: V \rightarrow \mathbf{Q}^{+}\) be an arbitrary function. Define the largest degree-proportional function relative to \(w\) in the graph \(G\) as follows:

1. Remove from the graph all vertices of degree 0;

2. Among the remaining vertices, compute the value \(c=\min \left\{ \frac{w(v)}{\operatorname {deg}(v)}\right\}\).

Then the function \(t(v)=c \cdot \operatorname {deg}(v)\) is the one sought.

Define \(w^{\prime }(v)=w(v)-t(v)\) as the residual weight function.

We now present an algorithm that splits the original weight function into degree-proportional functions and builds a vertex cover.

Algorithm 2 Level algorithm for the weighted vertex cover problem (\(G=(V, E), w: V \rightarrow \mathbb {Q}^{+}\))

• \(\operatorname{Sol} \gets \varnothing\), \(i \gets 0\)
• \(w'(v) \gets w(v)\) for all \(v \in V\) (initialize residual weights)
• \(D_0 \gets \{v \in V \mid \deg(v) = 0\}\) (vertices of degree \(0\) never join the cover)
• \(V_0 \gets V \setminus D_0\) (remove vertices of degree \(0\))
• while \(V_i \neq \varnothing\) do
  • \(c \gets \min_{v \in V_i} \frac{w'(v)}{\deg_i(v)}\) (\(\deg_i\) is the degree in the current subgraph \(G_i = G[V_i]\))
  • for each \(v \in V_i\) do
    • \(t_i(v) \gets c \cdot \deg_i(v)\) (amount subtracted for the vertex)
    • \(w'(v) \gets w'(v) - t_i(v)\) (update the residual weight)
  • \(W_i \gets \{v \in V_i \mid w'(v) = 0\}\) (vertices that reached zero residual weight)
  • \(\operatorname{Sol} \gets \operatorname{Sol} \cup W_i\) (add these vertices to the solution)
  • \(V_{i+1} \gets V_i \setminus W_i\)
  • \(D_{i+1} \gets \{v \in V_{i+1} \mid \deg_{G[V_{i+1}]}(v) = 0\}\) (vertices of degree \(0\) after removing \(W_i\))
  • \(V_{i+1} \gets V_{i+1} \setminus D_{i+1}\) (remove vertices of degree \(0\))
  • \(i \gets i + 1\)
• return \(\operatorname{Sol}\)

2.2.3 Accuracy bounds

Theorem 3 The local ratio algorithm and the level algorithm are \(2\)-approximation algorithms for the vertex cover problem.

Mn-proofProof

We prove the statement for the level algorithm. Let \(t_{0}, \ldots , t_{k-1}\) be the degree-proportional functions on the graphs \(G_{0}, \ldots , G_{k-1}\) constructed by the algorithm. Then \(\operatorname {Sol}=W_{0} \cup \ldots \cup W_{k-1}\) is the solution obtained by the algorithm, and \(V \backslash \operatorname {Sol}=D_{0} \cup \ldots \cup D_{k}\).

First we show that the set \(\operatorname {Sol}\) is a vertex cover of the graph \(G\). Suppose not. Then there is an edge \((u, v)\) such that \(u \in D_{i}, v \in D_{j}\) for some \(i, j\). Say \(i \leq j\); the vertex \(v\) is removed later, so at time \(i\) both vertices are still present, and the edge \((u, v)\) lies in \(G_{i}\). This contradicts the fact that the degree of \(u\) in \(G_i\) is zero.

Let \(C^{*}\) be an optimal vertex cover. We prove that \(w(\operatorname {Sol}) \leq 2 \cdot \operatorname {OPT}\). Consider a vertex \(v \in \operatorname {Sol}\). Let \(v \in W_{j}\) for some \(j\); its residual weight became zero, so

\[ w(v)=\sum _{i \leq j} t_{i}(v) \]

Now consider a vertex \(v \in V \backslash \mathrm{Sol}\). Let \(v \in D_{j}\) for some \(j\); the residual weight is nonnegative, so

\[ w(v) \geq \sum _{i<j} t_{i}(v) \]

Note that in each layer \(i\) the set of vertices \(C^{*} \cap V_{i}\) is a cover of \(G_{i}\), since \(G_{i}\) is an induced subgraph (\(C^*\) covers every edge of \(G_i\), and the covering endpoint itself lies in \(V_i\)). Applying the lemma above to the degree-proportional function \(t_i\) on the graph \(G_i\), we get \(t_{i}\left(\operatorname {Sol} \cap V_{i}\right) \leq t_i(V_i) \leq 2 \cdot t_{i}\left(C^{*} \cap V_{i}\right)\). Finally:

\[ w(\operatorname {Sol}) = \sum _{i=0}^{k-1} t_{i}\left(\mathrm{Sol} \cap V_{i}\right) \leq 2 \sum _{i=0}^{k-1} t_{i}\left(C^{*} \cap V_{i}\right) \leq 2 \cdot w\left(C^{*}\right) \]

(in the first equality the weight of each vertex \(v \in W_j\) is decomposed over layers \(i \leq j\), and the last inequality uses the fact that for every vertex \(\sum_{i \colon v \in V_i} t_i(v) \leq w(v)\)).

For the local ratio algorithm the bound follows from the graph-splitting theorem: at each step the subtracted weight function \(w_1\) is concentrated on the two endpoints of a single edge \((u,v)\) (\(\varepsilon\) on each), and any vertex cover has \(w_1\)-weight at least \(\varepsilon\), whereas the \(w_1\)-weight of any set of vertices is at most \(2\varepsilon\) — that is, with respect to each subtracted function an arbitrary cover is a \(2\)-approximation. The algorithm’s solution consists of vertices with zero residual weight, so its weight equals the sum of the weights over the subtracted functions, and by the splitting theorem it is a \(2\)-approximation for the original weights.

Let us give an example on which this bound is achieved. Let \(K_{n, n}\) be a complete bipartite graph in which all vertices have unit weight. The level algorithm will place all \(2n\) vertices of \(K_{n, n}\) into the cover, whereas the optimal solution consists of the vertices of a single side.

3 Exercises

ProblemProblem 1

From the words chanterelle, honey fungus, truffle, champignon, fly agaric, blusher, saffron milk cap, eucalyptus, birch, thuja, sequoia, linden, gooseberry, choose a subset of words so that together they contain all the vowel letters and the total number of letters is minimized. Formulate this as a set cover problem and solve it using Chvátal’s algorithm.

ProblemProblem 2

Construct an example on which the bound for Chvátal’s algorithm for the set cover problem is achieved, even when every set has weight 1.

ProblemProblem 3

Consider instances of the cover problem in which each element belongs to at most \(3\) subsets. Construct a \(3\)-approximation level algorithm for such instances.

ProblemProblem 4

A complete antisymmetric graph is a directed graph \(G=(V, E)\) in which, for every pair of vertices \(u, v \in V\), exactly one of the arcs \((u, v) \in E\) or \((v, u) \in E\) is present. A feedback vertex set in \(G\) is a set of vertices whose removal makes the graph acyclic. Propose a \(3\)-approximation algorithm for finding a feedback vertex set in an antisymmetric graph.

HintHint

Show that it suffices to eliminate cycles of length 3.