# Maximum Positive Negative Set Cover Problem

I am considering the following problem.

Input: Given two disjoint subsets $$A$$ and $$B$$ and a collection $$C$$ of $$k$$ sets $$S_1,S_2,\ldots,S_k$$ where $$S_i \subseteq A \cup B$$ for all $$i=1\ldots k$$.

Solution form: A collection $$C' \subseteq C$$.

Objective: Maximize $$\left|\left(\bigcup\limits_{c \in C'} c\right) \cap A\right| + \left|B \setminus\left(\bigcup\limits_{c \in C'} c\right)\right|$$.

That is, maximize the nodes in A covered plus the nodes in B not covered.

I am wondering the hardness of approximation.

Related work:

If we consider minimizing the objective, it becomes the problem studied in the following paper.

Miettinen, Pauli. "On the positive–negative partial set cover problem." Information Processing Letters 108.4 (2008): 219-221

• Maximizing the covered nodes in A plus uncovered nodes in B is the same as minimizing the uncovered nodes in A plus covered nodes in B. But then if you swap A and B, that's just the problem you said was already studied in the paper you listed. – Mikhail Rudoy Jun 7 '19 at 2:50
• @MikhailRudoy In terms of the optimal solution, they are the same. Buf from the purpose of approximation, I think they are different. Could you provide some details? – Arthur Jun 7 '19 at 15:19

This problem has a few simple constant-factor approximation algorithms, such as the trivial algorithm that picks the $$C' \in \{\emptyset, C\}$$ with a higher objective score.

Here's a loose constant-factor hardness result. No significant effort was put into optimizing the constant. I'm sure others can find something tighter.

Let $$G = (V,E)$$ be an instance of Max-Cut. We construct $$A$$, $$B$$, and $$C$$ as follows:

• $$A$$ contains two vertices, $$a_{u,v}$$ and $$a_{v,u}$$, for each $$(u,v) \in E$$.
• $$B$$ contains two vertices, $$b_{u,v}$$ and $$b_{v,u}$$, for each $$(u,v) \in E$$.
• $$C$$ contains one set $$c_v$$ for each $$v \in V$$.
• $$c_v := \bigcup_{u \in \mathcal{N}(v)} \{a_{u,v}, a_{v,u}, b_{u,v}\}$$, where $$\mathcal{N}(v)$$ denotes the neighborhood of $$v$$ in $$E$$.

Every subset of $$C$$ naturally corresponds to a collection of vertices from $$V$$ (i.e. via the subscripts). Call the set of vertices in this solution $$V_C$$.

Now for every edge $$(u,v) \in E$$, we count how many vertices from $$\{a_{u,v}, a_{v,u}, b_{u,v}, b_{v,u}\}$$ belong to $$S = \left(A\cap \left(\bigcup_{c \in C} c\right)\right) \cup \left(B \setminus \left(\bigcup_{c \in C} c\right)\right)$$.

• If $$u \in V_C$$ and $$v \in V_C$$, then only $$a_{u,v}$$ and $$a_{v,u}$$ are in $$S$$.
• If $$u \in V_C$$ and $$v \not\in V_C$$, then $$a_{u,v}$$, $$a_{v,u}$$, and $$b_{u,v}$$ are in $$S$$.
• If $$u \not\in V_C$$ and $$v \in V_C$$, then $$a_{u,v}$$, $$a_{v,u}$$, and $$b_{v,u}$$ are in $$S$$.
• If $$u \not\in V_C$$ and $$v\not\in V_C$$, then only $$b_{v,u}$$ and $$b_{u,v}$$ are in $$S$$.

Therefore, the total number of vertices in $$S$$ is equal to $$2|E| + |\textrm{Cut}_E(V_C, V \setminus V_C)|$$. Thus, the optimal solution involves a Max-Cut computation.

If it is hard to distinguish Max-Cut instances with optimal value $$\geq \alpha |E|$$ from those with value $$\leq \beta |E|$$, then for your problem it's hard to distinguish instances with optimal value $$\geq (2+\alpha)|E|$$ from those with value $$\leq (2+\beta)|E|$$, for a hardness of $$\frac{2 + \beta}{2 + \alpha} = 1 - \frac{\alpha - \beta}{2 + \alpha} < 1 - (\alpha - \beta)/3$$.

At this point we can plug in our favorite result on the hardness of max cut. E.g. UGC implies that we can choose $$\alpha - \beta > .1$$,$$^*$$ so this gives us a UGC gap of something less than $$1-(1/10)/3 = 29/30$$. Similar results can be had for NP-hardness, albeit with a slightly bigger constant.

$$^*$$ Note: this is not quite $$1-\alpha_{GW}$$, since $$\alpha_{GW}$$ measures the gap ratio rather than the gap difference.

• Thank you for your answer. I can follow the first part but I am not familiar with the hardness of Max-Cut derived from UGC. Could you provide any reference for this part of knowledge? – Arthur Jun 9 '19 at 2:34
• The result was first shown in theorem 1 of Khot et. al. Additionally, here are some lecture notes that might help. What they show is that for each $\rho \in [-1,1]$, UGC implies that Max-Cut is hard with (using the above notation) $\alpha = (1-\rho)/2$ and $\beta = \tfrac{\cos^{-1} \rho}{\pi}$. We can find the optimal choice of $\alpha$ and $\beta$ by plotting. – Yonatan N Jun 9 '19 at 2:51
• Thank you very much. Suppose we require that $|C|=k$ under the cardinality constraints. Do you think it has a stronger hardness result? – Arthur Jun 9 '19 at 2:54
• I have another 'small' question concerning the DkS problem. Given an instance of DkS, suppose that I am considering the objective function $k+f(S)$, where $f(S)$ is the total number of edges induced by a node-set $S$. Can we draw some conclusion on approximation hardness? Thank you. – Arthur Jun 14 '19 at 14:37