Does turning the $\ge$ to $=$ sign increase the hardness of solving the Set-Cover problem?

Question

The set cover problem, a well-known combinatorial issue, involves selecting the fewest number of sets from a collection $ S = \{s_1, \dots, s_m\} $, covering a universe $ U = \bigcup_{i=1}^m s_i $. Its LP-relaxation is solvable in polynomial time with an LP-solver through the formulation:

$ \begin{array}{lll} \min & \sum_{i=1}^m x_i \\ \text{s.t.} & \sum_{i: j \in s_i} x_i \geq 1 & \forall j \in U \\ & x_i \geq 0 & \forall i \\ \end{array} $

Out of pure mathematical curiosity, I just want to ask you about the hardness implication from which I purposefully changing the $\ge$ sign to $=$ sign for all set cover constrains.

For example, changing from this:

\begin{array}{*{20}{c}} {\bf{P_1}:\mathop {\min }\limits_{{x_i} \in \left\{ {0,1} \right\}} }&{{x_1} + {x_2} + {x_3} + {x_4}}\\ {}&{{x_1} + {x_2} \ge 1}\\ {}&{{x_2} + {x_3} \ge 1}\\ {}&{{x_1} + {x_3} + {x_4} \ge 1}\\ {}&{{x_1} + {x_4} \ge 1}\\ {}&{{x_2} + {x_3} + {x_4} \ge 1} \end{array}

To this:

\begin{array}{*{20}{c}} {\bf{P_2}\mathop {\min }\limits_{{x_i} \in \left\{ {0,1} \right\}} }&{{x_1} + {x_2} + {x_3} + {x_4}}\\ {}&{{x_1} + {x_2} = 1}\\ {}&{{x_2} + {x_3} = 1}\\ {}&{{x_1} + {x_3} + {x_4} = 1}\\ {}&{{x_1} + {x_4} = 1}\\ {}&{{x_2} + {x_3} + {x_4} = 1} \end{array}

At first glance, it seems that finding the set of $x_i$ to satisfied $\bf{P_2}$ is just XOR-SAT which can be done in polynomial time by Gaussian elimination in $GF(2)$. However, I am not sure if this make $\bf{P_2}$ easier or harder to solver than $\bf{P_1}$. However, I also have a feeling that since they are both binary integer problem, they are both NP-Hard problem.

From my perspective, it seems that $=$ sign ask me to cover one element using exactly one subset. This has turn this problem into some kind to multi set cover problem in which an element is asked to be covered by exactly one subset. In contrast, $\ge$ allow to cover one element using multiple overlapping subsets. This fact itself just trigger an interesting question on whether the classical greedy algorithm can still be applied on $\bf{P_2}$.

Therefore, my question is: "Does turning the $\ge$ to $=$ sign increase the hardness of solving the Set-Cover problem ?"

Could anyone advise on the best approach on how to analyze the different in term of hardness ?

Answer 1

I am unsure if I understand your question correctly, but let me give some points.

Given a finite set $S$ and a family $E = \{S_1, \cdots, S_n\}$ of its subsets. The pair $H = (S, E)$ is often called a hypergraph. By analogy with graphs, the elements of the set $S$ are called vertices, and the subsets in $E$ are called hyperedges. Let us assign to each hyperedge $S_j$ its associated cost $c_j$. The set packing problem is to find a packing with the maximum total cost of its hyperedges. The set covering (resp., set partitioning) problem is to find a cover (resp., partition) with the minimum total cost of its hyperedges. From a mathematical point of view:

$$\text{Set packing} \rightarrow \quad \max \{ c^T x: Ax \leq e, x \in \{0,1\}^n \}$$ $$\text{Set partitioning} \rightarrow \quad \min\{ c^T x: Ax = e, x \in \{0,1\}^n \}$$ $$\text{Set covering} \rightarrow \quad \min\{ c^T x: Ax \geq e, x \in \{0,1\}^n \}$$

However, all of those are NP-hard in its essence, it already depends on how you would like to use those in your math formulation. Also, be aware that you cannot apply those instead of each other as the problem may entirely change in the different one.

For example, in the resource assignment problem if you want to assign a task exactly to one resource and if you change the partitioning constraint, e.g. $\sum x_{i,j} = 1$ (assigning task $j$ to resource $i$), to the covering one, $\sum x_{i,j} \geq 1$, the problem and its solution are entirely different from the original definition.