2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mikhail Rudoy Jun 7 at 2:50
  • $\begingroup$ @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? $\endgroup$ – Arthur Jun 7 at 15:19
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Arthur Jun 9 at 2:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Yonatan N Jun 9 at 2:51
  • $\begingroup$ Thank you very much. Suppose we require that $|C|=k$ under the cardinality constraints. Do you think it has a stronger hardness result? $\endgroup$ – Arthur Jun 9 at 2:54
  • $\begingroup$ 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. $\endgroup$ – Arthur Jun 14 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.