Vertex subset of maximum size

Question

I was wondering if this problem has a name and/or it has been already studied.

Problem: Given an undirected graph $G=(V,E)$, a function $f: V \to \mathbb N$, and a natural number $k$ : Does there exist a subset $S\subseteq V$ with $|S| \geqslant k$, such that $$ \forall v \in V \,:\, \biggl|\;\Bigr(N(v) \cup \{v\}\Bigr) \cap S\;\biggr| \;\leqslant\; f(v) \;?$$

Question. Is this problem NP-complete? Are there good approximation algorithms?

Answer 1

I think a general polynomial time solution to this would be able to be used to solve k-SAT.

For each variable create two vertexes corresponding to true and false and connect them by an edge. Start by assigning k to to the number of variables (half the number of vertexes), and each of their f values to 1. Let not being in S mean true or false. Now we have a graph where each variable has to be either true or false.

For each OR operation on x variables create one vertex and connect it to the appropriate true/false vertexes.

For each OR operation create a large number Z of auxilary vertexes with an f value of 1, and connect each by an edge to the OR vertex. Increment k by Z for each OR operation. We can see this will force the OR operation vertex to not be a member of S, and all the auxilary vertexes to be in S.

Now assign the f value of each OR vertex to Z+x-1. Z of these will be taken by the auxilary vertexes. The OR vertex is not in S, so this means at maximum x-1 of the connected variable vertexes can be in S, so at least one of the variable nodes connected to an OR vertex will have to not be in S.

Answer 2

There's a couple of things I want to add to this discussion/Q&A. First I think it's an interesting exercise to rewrite user10310's reduction from SAT to this problem in a more formal manner. The second bit is an alternative NP-completeness proof that might be a useful starting point for looking for approximation results.

For convenience, let's give this problem a name (the most important step in any complexity result!). Unfortunately, I can't think of a good proper name, so for now I'm going to call it OUR PROBLEM, or OP for short, because that's a nice pun.

Lemma 1 OP $\in$ NP.

Proof. Given a set $S$ we can check that each vertex $v$ in the graph has at most $f(v)$ neighbours in $S$ in polynomial time.

Lemma 2 3-SAT $\leq_{P}$ OP.

Proof. Given an instance $I$ of 3-SAT with variable set $X=\{x_{1},\ldots,x_{n}\}$ and clause set $C=\{c_{1},\ldots,c_{m}\}$, we construct an instance $I'$ of OP as follows:

We create a graph $G=(V,E)$ where

• For each variable $x_{i}\in X$ we have two vertices $x_{i}^{+}$ and $x_{i}^{-}$ in $V$. Denote this subset of $V$ as $V_{X}$.
• For each clause $c_{j}\in C$ we have a vertex $c_{j}\in V$. Denote the set of clause vertices as $V_{C}$.
• In addition there is a set of vertices $V_{Z}$ with $|V_{Z}| = 2n+m+1$.
• For each pair of vertices $x_{i}^{+}$ and $x_{i}^{-}$, we have $x_{i}^{+}x_{i}^{-} \in E$.
• For each clause $c_{j} \in C$, if the literal $x_{i}$ is in the clause we have $c_{j}x_{i}^{+} \in E$, if the literal $\neg x_{i}$ is in the clause we have $c_{j}x_{i}^{-}\in E$.
• For every pair of vertices $z \in V_{Z}$ and $c_{j} \in V_{C}$ we have $zc_{j}\in E$.

We then set the function $f:V\rightarrow\mathbb{N}$ as follows: $$ f(v) := \left\{\begin{array}{ll}1&\text {if }v\in V_{X}.\\2n+m+3&\text{if }v\in V_{C}\\1&\text{if }v\in V_{Z}\end{array}\right. $$

Finally we choose $k$ to be $3n+m+1$.

Now we establish certain properties of a solution set $S$ for $I'$.

Proposition At most $n$ vertices of $V_{X}$ are in $S$.

For each pair $x_{i}^{+}$, $x_{i}^{-}$ we can only have one vertex in $S$, otherwise both vertices violate their $f$ value constraint.

Proposition Any solution $S$ contains all the vertices of $V_{Z}$ and none of the vertices of $V_{C}$.

Clearly as $k$ is so large, we need at least some vertices of $V_{Z}$ in $S$, but then if any vertices of $V_{C}$ are in $S$, there is some vertex in $V_{Z}\cap S$ that has at least two vertices in its closed neighbourhood in $S$, which exceeds its $f$ value of $1$. Thus we can have no vertices of $V_{C}$ in $S$. Then $S$ can contain only vertices of $V_{Z}\cup V_{X}$. If we do not include all vertices of $V_{Z}$ in $S$, we have $|S| \leq 3n+m$, thus $S$ is not of size at least $k$, and is therefore not a solution.

So we can see the solution set $S$ is quite constrained, and must take all of $V_{Z}$ and half of $V_{X}$ (which will correspond to a truth assignment).

Proposition If $I$ is a Yes-instance of 3-SAT then $I'$ is a Yes-instance of OP.

If $I$ is a Yes-instance, we have a truth assignment $A:X\rightarrow\{T,F\}$ that satisfies the formula. We construct a set $S \subseteq V$ by taking the vertices of $V_{Z}$ and for each variable $x_{i} \in X$, if $A(x) = T$, we add $x_{i}^{-}$ to $S$, otherwise we add $x_{i}^{+}$. This is clearly a suitable set $S$.

Proposition If $I'$ is a Yes-instance of OP then $I$ is a Yes-instance of 3-SAT.

The set $S$ that constitutes a solution for $I'$ contains $n$ vertices of $V_{X}$, and more particularly, one vertex out of each variable pair. Moreover, as $f(c_{j}) = 3n+m+2$ for all $c_{j}\in V_{C}$, we know that $c_{j}$ is adjacent to at least one vertex in $V_{X}$ that is not in $S$. This vertex then gives us the satisfying assignment for the corresponding variable.

Theorem 3 OP is NP-complete.

Proof. By combining lemmas 1 & 2.

Now I want prove the same thing, but via an alternate route.

Note that the dual problem is the following: Given a graph $G$, a function $g:V(G)\rightarrow\mathbb{N}$ and an integer $k'$, is there a set $S\subseteq V(G)$ with $|S|\leq k'$ such that for all $v \in V$ we have $|N[v]\cap S|\geq g(v)$. To see that this is the dual, starting with OP, we just take $k' = n-k$ and $g(v) = d(v)-f(v)$, where $d(v)$ is the degree of $v$. We then immediately get NP-completeness for OP and dual-OP by observing that DOMINATING SET is a special case of dual-OP; we just take $g(v)$ to be $1$ for all vertices.

Then we know that dual-OP has no $O(\log n)$ approximation unless P=NP (if I recall the result correctly). Unfortunately this doesn't say anything immediately about OP, but is a possible start.