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

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

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

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

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

CC BY-SA 3.0
2012-08-16T04:08:49.100Z
I think this almost works, but I can't quite justify the argument that a solution to the graph problem implies a solution to the SAT problem (Say $|X| \geq |C|$, then I can't see why you can't maybe pick both variable vertices and still get $|S| \geq k$).
Luke Mathieson
CC BY-SA 3.0
2012-08-16T04:10:02.920Z
I'm also going to attempt a rewrite of your construction, please double and triple check that I don't mess anything up.
Luke Mathieson
CC BY-SA 3.0
2012-08-16T04:11:48.323Z
I'll confess there is a bug, but I think it is fixable.
Andrew Tomazos
CC BY-SA 3.0
2012-08-16T04:35:52.840Z
I think it may be too. Perhaps there is some argument that the sort of situation I proposed leads to a contradiction. It's clear that a satisfying assingment gives us the $S$ as expected, so that direction is firm.
Luke Mathieson
CC BY-SA 3.0
2012-08-16T04:42:47.053Z
Its fixed now..
Andrew Tomazos
CC BY-SA 3.0
2012-08-16T04:49:34.563Z
The trick is to understand that k is a floor on the number of nodes and f is a ceiling on the number of nodes.  By making them work against each other hard enough we can force the machine to search an exponential number of combinations.
Andrew Tomazos
CC BY-SA 3.0
2012-08-16T05:14:31.780Z
Yeah, that seems to work now.
Luke Mathieson
CC BY-SA 3.0
2012-08-16T20:25:23.013Z
It's possible to show that $Z = 1$ suffices. We can do this by showing that there is no decrease in the optimum if we restrict ourselves to sets containing all of the auxiliary nodes and none of the nodes corresponding to OR-clauses. I suspect that this may allow us to generalize the problem to correctly guess a satisfying assignment for any NOR-circuit (a CNF formula may be represented as a NOR-circuit of depth 2), including the intermediate outcomes of all of the gates arising from the satisfying assignment.
Niel de Beaudrap
CC BY-SA 3.0
2012-08-16T20:52:27.903Z
@NieldeBeaudrap: Yes you are correct.  I guess having a large Z it is easier to see that the OR vertex can never be in S - which is made true independent of its f value or its other nonauxiliary connections.
Andrew Tomazos
CC BY-SA 3.0
2012-08-16T02:19:27.963Z
2012-08-16T04:59:23.600Z
2012-08-16T04:59:23.600Z
Andrew Tomazos
<p>There's a couple of things I want to add to this discussion/Q&amp;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.</p>

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

<p><b>Lemma 1</b> OP $\in$ NP.</p>

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

<p><b>Lemma 2</b> 3-SAT $\leq_{P}$ OP.</p>

<p><i>Proof.</i> 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:</p>

<p>We create a graph $G=(V,E)$ where</p>

<ul>
<li>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}$.</li>
<li>For each clause $c_{j}\in C$ we have a vertex $c_{j}\in V$. Denote the set of clause vertices as $V_{C}$.</li>
<li>In addition there is a set of vertices $V_{Z}$ with $|V_{Z}| = 2n+m+1$.</li>
<li>For each pair of vertices $x_{i}^{+}$ and $x_{i}^{-}$, we have $x_{i}^{+}x_{i}^{-} \in E$.</li>
<li>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$.</li>
<li>For every pair of vertices $z \in V_{Z}$ and $c_{j} \in V_{C}$ we have $zc_{j}\in E$.</li>
</ul>

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

<p>Finally we choose $k$ to be $3n+m+1$.</p>

<p>Now we establish certain properties of a solution set $S$ for $I'$.</p>

<p><b>Proposition</b> At most $n$ vertices of $V_{X}$ are in $S$.</p>

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

<p><b>Proposition</b> Any solution $S$ contains all the vertices of $V_{Z}$ and none of the vertices of $V_{C}$.</p>

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

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

<p><b>Proposition</b> If $I$ is a Yes-instance of 3-SAT then $I'$ is a Yes-instance of OP.</p>

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

<p><b>Proposition</b> If $I'$ is a Yes-instance of OP then $I$ is a Yes-instance of 3-SAT.</p>

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

<p><b>Theorem 3</b> OP is NP-complete.</p>

<p><i>Proof.</i> By combining lemmas 1 &amp; 2.</p>

<p>Now I want prove the same thing, but via an alternate route. </p>

<p>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 <i>dual</i>-OP by observing that DOMINATING SET is a special case of <i>dual</i>-OP; we just take $g(v)$ to be $1$ for all vertices.</p>

<p>Then we know that <i>dual</i>-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.</p>

CC BY-SA 3.0
2012-08-19T02:41:25.157Z
2012-08-19T02:47:16.790Z
2012-08-19T02:47:16.790Z
Luke Mathieson
<p>I was wondering if this problem has a name and/or it has been already studied.</p>

<blockquote>
  <p><strong>Problem:</strong> Given an undirected graph $G=(V,E)$, a function $f: V \to \mathbb N$, and a natural number $k$&nbsp;:
  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) \;?$$</p>
</blockquote>

<p><em>Question.</em>
Is this problem NP-complete? Are there good approximation algorithms?</p>

CC BY-SA 3.0
2012-08-15T07:13:57.023Z
I was just about to post the obvious answer to your question (PTIME), but then realised that there's a few things wrong. I think the problem as stated is not what you meant, and there's a couple of ways it can go: $\forall v\in V$ $|N_{S}[v]|\leq f(v)$, or $\forall v \in S$ $|N_{S}[v]| \leq f(v)$. The option $\forall v \in S$ $N[v] \leq f(v)$ is the far-too-easy one. (Where $N_{S}[v]$ is the closed neighbourhood of $v$ restricted to $S$).
Luke Mathieson
CC BY-SA 3.0
2012-08-15T08:51:13.193Z
Thinking a little more, you can dispense with the closed neighbourhood, and just use the open neighbourhood (i.e. we can define a new function $f'$ by $f'(v) = f(v)-1$, as the case where $f(v) = 0$ is trivially dealt with). Also, of the options I thought of, the $\forall v \in S$ $|N_{S}(v)|\leq f(v)$ one is a generalisation of Independent Set - just pick $f(v) = 0$ for all $v$.
Luke Mathieson
CC BY-SA 3.0
2012-08-15T13:15:16.957Z
I don't know how to delete this answer. Now the problem statement is alright so this answer is useless. Can anyone delete it please?
john
CC BY-SA 3.0
2012-08-15T13:37:03.030Z
Thanks Niel. I have now corrected the original statement.
john
CC BY-SA 3.0
2012-08-16T00:01:45.547Z
John, you can delete your comments/posts if you register your account. Registering is quite simple, you just need an OpenId (e.g. an account on GMail, Facebook, or Yahoo).
Kaveh
CC BY-SA 3.0
2012-08-16T01:43:34.017Z
Any subset of an S that satisfies the equation, also satisfies the equation - so you can change the constraint to $|S| = k$.
Andrew Tomazos
CC BY-SA 3.0
2012-08-16T03:21:13.160Z
Natural numbers are not well defined whether or not they include zero.  Better to use "positive integers" or "nonnegative integers" as appropriate.
Andrew Tomazos
CC BY-SA 3.0
2012-08-19T20:12:56.630Z
@Kaveh: Just to add, one can create an OpenID also on Stack Exchange.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-21T20:01:07.237Z
@Niel: I reverted your edit in revision 7 where you added a name “Maximum Load” to the problem.  I do not know whether this is the standard name for the problem or you came up with a suggestion, but either way, stating a name in the question contradicts the “I was wondering if this problem has a name…” part of the question.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-21T22:35:24.450Z
@TsuyoshiIto: fair enough, and good catch. (It was an improvised name.)
Niel de Beaudrap
<cc.complexity-theory><ds.algorithms><graph-theory><approximation-algorithms><time-complexity>
Vertex subset of maximum size
John
# Vertex subset of maximum size

(Asked by: username_0 on 2012-08-15)

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?

**Tags:** cc.complexity-theory, ds.algorithms, graph-theory, approximation-algorithms, time-complexity
> **Comments:**
> **username_1**: I was just about to post the obvious answer to your question (PTIME), but then realised that there's a few things wrong. I think the problem as stated is not what you meant, and there's a couple of ways it can go: $\forall v\in V$ $|N_{S}[v]|\leq f(v)$, or $\forall v \in S$ $|N_{S}[v]| \leq f(v)$. The option $\forall v \in S$ $N[v] \leq f(v)$ is the far-too-easy one. (Where $N_{S}[v]$ is the closed neighbourhood of $v$ restricted to $S$).  
> **username_1**: Thinking a little more, you can dispense with the closed neighbourhood, and just use the open neighbourhood (i.e. we can define a new function $f'$ by $f'(v) = f(v)-1$, as the case where $f(v) = 0$ is trivially dealt with). Also, of the options I thought of, the $\forall v \in S$ $|N_{S}(v)|\leq f(v)$ one is a generalisation of Independent Set - just pick $f(v) = 0$ for all $v$.  
> **username_2**: I don't know how to delete this answer. Now the problem statement is alright so this answer is useless. Can anyone delete it please?  
> **username_2**: Thanks Niel. I have now corrected the original statement.  
> **username_3**: John, you can delete your comments/posts if you register your account. Registering is quite simple, you just need an OpenId (e.g. an account on GMail, Facebook, or Yahoo).  
> **username_4**: Any subset of an S that satisfies the equation, also satisfies the equation - so you can change the constraint to $|S| = k$.  
> **username_4**: Natural numbers are not well defined whether or not they include zero.  Better to use "positive integers" or "nonnegative integers" as appropriate.  
> **username_5**: @Kaveh: Just to add, one can create an OpenID also on Stack Exchange.  
> **username_5**: @Niel: I reverted your edit in revision 7 where you added a name “Maximum Load” to the problem.  I do not know whether this is the standard name for the problem or you came up with a suggestion, but either way, stating a name in the question contradicts the “I was wondering if this problem has a name…” part of the question.  
> **username_6**: @TsuyoshiIto: fair enough, and good catch. (It was an improvised name.)  

---

## 2 answers

### Answer by username_4 on 2012-08-16. Score: 6

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.

> **Comments:**
> **username_1**: I think this almost works, but I can't quite justify the argument that a solution to the graph problem implies a solution to the SAT problem (Say $|X| \geq |C|$, then I can't see why you can't maybe pick both variable vertices and still get $|S| \geq k$).  
> **username_1**: I'm also going to attempt a rewrite of your construction, please double and triple check that I don't mess anything up.  
> **username_4**: I'll confess there is a bug, but I think it is fixable.  
> **username_1**: I think it may be too. Perhaps there is some argument that the sort of situation I proposed leads to a contradiction. It's clear that a satisfying assingment gives us the $S$ as expected, so that direction is firm.  
> **username_4**: Its fixed now..  
> **username_4**: The trick is to understand that k is a floor on the number of nodes and f is a ceiling on the number of nodes.  By making them work against each other hard enough we can force the machine to search an exponential number of combinations.  
> **username_1**: Yeah, that seems to work now.  
> **username_6**: It's possible to show that $Z = 1$ suffices. We can do this by showing that there is no decrease in the optimum if we restrict ourselves to sets containing all of the auxiliary nodes and none of the nodes corresponding to OR-clauses. I suspect that this may allow us to generalize the problem to correctly guess a satisfying assignment for any NOR-circuit (a CNF formula may be represented as a NOR-circuit of depth 2), including the intermediate outcomes of all of the gates arising from the satisfying assignment.  
> **username_4**: @NieldeBeaudrap: Yes you are correct.  I guess having a large Z it is easier to see that the OR vertex can never be in S - which is made true independent of its f value or its other nonauxiliary connections.  

---

### Answer by username_1 on 2012-08-19. Score: 3

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.


---

