<p>This problem has a few simple constant-factor approximation algorithms, such as the trivial algorithm that picks the <span class="math-container">$C' \in \{\emptyset, C\}$</span> with a higher objective score.</p>

<p>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.</p>

<hr>

<p>Let <span class="math-container">$G = (V,E)$</span> be an instance of Max-Cut. We construct <span class="math-container">$A$</span>, <span class="math-container">$B$</span>, and <span class="math-container">$C$</span> as follows:</p>

<ul>
<li><span class="math-container">$A$</span> contains two vertices, <span class="math-container">$a_{u,v}$</span> and <span class="math-container">$a_{v,u}$</span>, for each <span class="math-container">$(u,v) \in E$</span>.</li>
<li><span class="math-container">$B$</span> contains two vertices, <span class="math-container">$b_{u,v}$</span> and <span class="math-container">$b_{v,u}$</span>, for each <span class="math-container">$(u,v) \in E$</span>.</li>
<li><span class="math-container">$C$</span> contains one set <span class="math-container">$c_v$</span> for each <span class="math-container">$v \in V$</span>. </li>
<li><span class="math-container">$c_v := \bigcup_{u \in \mathcal{N}(v)} \{a_{u,v}, a_{v,u}, b_{u,v}\}$</span>, where <span class="math-container">$\mathcal{N}(v)$</span> denotes the neighborhood of <span class="math-container">$v$</span> in <span class="math-container">$E$</span>.</li>
</ul>

<p>Every subset of <span class="math-container">$C$</span> naturally corresponds to a collection of vertices from <span class="math-container">$V$</span> (i.e. via the subscripts). Call the set of vertices in this solution <span class="math-container">$V_C$</span>.</p>

<p>Now for every edge <span class="math-container">$(u,v) \in E$</span>, we count how many vertices from <span class="math-container">$\{a_{u,v}, a_{v,u}, b_{u,v}, b_{v,u}\}$</span> belong to <span class="math-container">$S = \left(A\cap \left(\bigcup_{c \in C} c\right)\right) \cup \left(B \setminus \left(\bigcup_{c \in C} c\right)\right)$</span>.</p>

<ul>
<li>If <span class="math-container">$u \in V_C$</span> and <span class="math-container">$v \in V_C$</span>, then only <span class="math-container">$a_{u,v}$</span> and <span class="math-container">$a_{v,u}$</span> are in <span class="math-container">$S$</span>.</li>
<li>If <span class="math-container">$u \in V_C$</span> and <span class="math-container">$v \not\in V_C$</span>, then <span class="math-container">$a_{u,v}$</span>, <span class="math-container">$a_{v,u}$</span>, and <span class="math-container">$b_{u,v}$</span> are in <span class="math-container">$S$</span>.</li>
<li>If <span class="math-container">$u \not\in V_C$</span> and <span class="math-container">$v \in V_C$</span>, then <span class="math-container">$a_{u,v}$</span>, <span class="math-container">$a_{v,u}$</span>, and <span class="math-container">$b_{v,u}$</span> are in <span class="math-container">$S$</span>.</li>
<li>If <span class="math-container">$u \not\in V_C$</span> and <span class="math-container">$v\not\in V_C$</span>, then only <span class="math-container">$b_{v,u}$</span> and <span class="math-container">$b_{u,v}$</span> are in <span class="math-container">$S$</span>.</li>
</ul>

<p>Therefore, the total number of vertices in <span class="math-container">$S$</span> is equal to <span class="math-container">$2|E| + |\textrm{Cut}_E(V_C, V \setminus V_C)|$</span>. Thus, the optimal solution involves a Max-Cut computation.</p>

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

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

<p><span class="math-container">$^*$</span> Note: this is not quite <span class="math-container">$1-\alpha_{GW}$</span>, since <span class="math-container">$\alpha_{GW}$</span> measures the gap ratio rather than the gap difference.</p>

CC BY-SA 4.0
2019-06-09T02:34:39.490Z
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
CC BY-SA 4.0
2019-06-09T02:51:11.643Z
The result was first shown in theorem 1 of [Khot et. al](https://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf). Additionally, [here are some lecture notes that might help](https://courses.cs.washington.edu/courses/cse533/05au/lecture19.pdf). 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](https://www.wolframalpha.com/input/?i=maximize+y%3D\(\(1-x\)%2F2+-+\(arccos+x\)%2Fpi\)).
Yonatan N
CC BY-SA 4.0
2019-06-09T02:54:47.653Z
Thank you very much. Suppose we require that $|C|=k$ under the cardinality constraints. Do you think it has a stronger hardness result?
Arthur
CC BY-SA 4.0
2019-06-14T14:37:14.517Z
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
CC BY-SA 4.0
2019-06-08T08:36:14.617Z
2019-06-20T05:45:55.090Z
2019-06-20T05:45:55.090Z
Yonatan N
<p>I am considering the following problem. </p>

<p><strong>Input</strong>: Given two disjoint subsets <span class="math-container">$A$</span> and <span class="math-container">$B$</span> and a collection <span class="math-container">$C$</span> of <span class="math-container">$k$</span> sets <span class="math-container">$S_1,S_2,\ldots,S_k$</span> where <span class="math-container">$S_i \subseteq A \cup B$</span> for all <span class="math-container">$i=1\ldots k$</span>.</p>

<p><strong>Solution form</strong>: A collection <span class="math-container">$C' \subseteq C$</span>.</p>

<p><strong>Objective</strong>: Maximize <span class="math-container">$\left|\left(\bigcup\limits_{c \in C'} c\right) \cap A\right| + \left|B \setminus\left(\bigcup\limits_{c \in C'} c\right)\right|$</span>.</p>

<p>That is, maximize the nodes in A covered plus the nodes in B not covered.</p>

<p>I am wondering the hardness of approximation.</p>

<p><strong>Related work:</strong></p>

<p>If we consider minimizing the objective, it becomes the problem studied in the following paper.</p>

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

CC BY-SA 4.0
2019-06-07T02:50:55.837Z
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
CC BY-SA 4.0
2019-06-07T15:19:11.700Z
@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
<approximation-hardness>
Maximum Positive Negative Set Cover Problem
Arthur
# Maximum Positive Negative Set Cover Problem

(Asked by: username_0 on 2019-06-07)

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*

**Tags:** approximation-hardness
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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?  

---

## 1 answers

### Answer by username_2 on 2019-06-08. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_2**: The result was first shown in theorem 1 of [Khot et. al](https://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf). Additionally, [here are some lecture notes that might help](https://courses.cs.washington.edu/courses/cse533/05au/lecture19.pdf). 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](https://www.wolframalpha.com/input/?i=maximize+y%3D\(\(1-x\)%2F2+-+\(arccos+x\)%2Fpi\)).  
> **username_0**: Thank you very much. Suppose we require that $|C|=k$ under the cardinality constraints. Do you think it has a stronger hardness result?  
> **username_0**: 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.  

---

