Verifying if a greedy solution is optimal for a specific instance (Set cover)

Question

Say I have an instance of the Set Cover problem, and use the typical greedy algorithm to obtain a solution.

Is there an efficient way of verifying if, for that particular instance, the given solution is optimal?

Answer 1

Let me formalize your problem, in two different ways:

GREEDY-SET-COVER: Given a Set Cover instance, does the greedy algorithm always produce a set cover of minimal size?

GREEDY-SET-COVER2: Given a Set Cover instance, does the greedy algorithm always produce a set cover of non-minimal size?

The two problems might seem complementary, but in fact it is not the case: if at some step of the algorithm there are several sets covering the same number of uncovered elements, the greedy algorithm must make a choice. In GREEDY-SET-COVER, we are asking whether all such choices lead to an optimal solution. The complement of GREEDY-SET-COVER2 asks whether some such choice leads to an optimal solution.

I will show that GREEDY-SET-COVER is $\mathsf{coNP}$-complete, and that GREEDY-SET-COVER2 is $\mathsf{NP}$-hard (but not necessarily in $\mathsf{NP}$). In fact, the same reduction will work for both.

Let me start by showing that GREEDY-SET-COVER is in $\mathsf{coNP}$. Given an instance of GREEDY-SET-COVER, all we need to do in order to show that it is a No instance is to give a transcript of the greedy algorithm together with a set cover which is smaller than what the greedy algorithm output. Unfortunately the same kind of witness doesn't work for GREEDY-SET-COVER2, since we would have to list all possible runs of the greedy algorithm.

In order to show that GREEDY-SET-COVER is $\mathsf{coNP}$-hard, we reduce from SAT. Let $\varphi$ be an instance of SAT with variables $x_1,\ldots,x_n$ and clauses $C_1,\ldots,C_m$. We first check whether there is an assignment to some variable which satisfies at least $m-1$ clauses. If it satisfies all clauses, the instance is satisfiable. Otherwise, the instance is satisfiable unless the remaining clause consists of this variable with opposite polarity. In both cases, we output an appropriate fixed instance of GREEDY-SET-COVER.

Suppose now that every assignment to a variable satisfies at most $m-2$ clauses. We will construct a Set Cover instance over the universe $\{x_1,\ldots,x_n,C_1,\ldots,C_m\}$ having the following sets:

• For each variable $x_i$ and each truth value $\tau$, there is a set $X_{i,\tau}$ which contains all clauses satisfied by this assignment to $\tau$, as well as the element $x_i$.
• The set $Y = \{C_1,\ldots,C_m\}$.

If the SAT instance is satisfiable, there is a set cover of size $n$, consisting of the sets $X_{1,\tau(1)},\ldots,X_{n,\tau(n)}$, where $\tau$ is a satisfying assignment. Otherwise, the optimal set covers have size $n+1$. The greedy algorithm first takes the set $Y$ (since all other sets contain at most $(m-2)+1 = m-1$ elements), and then takes one set each from every pair $X_{i,T},X_{i,F}$, in total producing a set cover of size $n+1$. This set cover has minimal size if and only if the SAT instance is unsatisfiable.

The exact same reduction works for GREEDY-SET-COVER2, since every run of the greedy algorithm must start with the set $Y$, and eventually produces a set cover of size $n+1$.