6
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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$). $\endgroup$ – Luke Mathieson Aug 15 '12 at 7:13
  • $\begingroup$ 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$. $\endgroup$ – Luke Mathieson Aug 15 '12 at 8:51
  • $\begingroup$ 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? $\endgroup$ – john Aug 15 '12 at 13:15
  • $\begingroup$ Thanks Niel. I have now corrected the original statement. $\endgroup$ – john Aug 15 '12 at 13:37
  • 1
    $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Aug 21 '12 at 20:01
6
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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$). $\endgroup$ – Luke Mathieson Aug 16 '12 at 4:08
  • $\begingroup$ I'm also going to attempt a rewrite of your construction, please double and triple check that I don't mess anything up. $\endgroup$ – Luke Mathieson Aug 16 '12 at 4:10
  • $\begingroup$ I'll confess there is a bug, but I think it is fixable. $\endgroup$ – Andrew Tomazos Aug 16 '12 at 4:11
  • $\begingroup$ 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. $\endgroup$ – Luke Mathieson Aug 16 '12 at 4:35
  • 1
    $\begingroup$ 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. $\endgroup$ – Niel de Beaudrap Aug 16 '12 at 20:25
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

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.