<p>I think the following is a polynomial-time algorithm based on maximum flow. Let $G(V,E), b, c$ be the input.</p>

<ul>
<li>Construct a directed bipartite graph $H(L,R,F)$ with $L$ and $R$ being the left and right partitions and $F$ being the directed edges <em>from</em> $L$ to $R$.</li>
<li>Let $|V| = n$. There are $n$ vertices in $L$ and $n$ vertices in $R$.</li>
<li>Each vertex $v \in V$ has a "copy" in $L$ (say $v_l$) and a copy in $R$ (say $v_r$).</li>
<li>If $(u,v) \in E$ add a directed edge from $u_l$ to $v_r$. Each such edge has capacity 1.</li>
<li>Add a "source" node $s$ and add directed edges from $s$ to each vertex in $L$. Each such edge has a capacity $b$.</li>
<li>Add a "sink" node $t$ and add directed edges from each vertex in $R$ to $t$. Each such edge has a capacity $c$.</li>
<li>Find maximum flow from $s$ to $t$.</li>
</ul>

<p>The given graph $G$ has a solution if and only if the max-flow computed above saturates every edge from $s$ to $L$, i.e., the flow on every edge from $s$ to $L$ is equal to $b$.</p>

CC BY-SA 2.5
2010-11-27T07:00:36.190Z
Indeed, this is precisely the intended solution when I assign this as a homework problem.
Jeffε
CC BY-SA 2.5
2010-11-26T19:17:03.667Z
2010-11-26T23:07:56.683Z
2010-11-26T23:07:56.683Z
Shiva Kintali
<p>Is the following decision problem NP-complete:</p>

<blockquote>
  <p>Let $G$ be an undirected graph and $b \le c$ 
  two integers. Is it possible to
  select for every vertex of $G$ exactly
  $b$ different neighbors such that no
  node is chosen more then $c$ times.</p>
</blockquote>

<p>The case $b = 1$ can be solved for any $c$ in polynomial time using maximal matching.</p>

<p>Motivation: Each node wants to place $b$ backups at different neighbors, but each node has only capacity to store $c$ backups.</p>

<cc.complexity-theory><np-hardness><graph-algorithms>
Is the backup problem NP-complete?
Volker Turau
# Is the backup problem NP-complete?

(Asked by: username_0 on 2010-11-26)

Is the following decision problem NP-complete:

> Let $G$ be an undirected graph and $b \le c$
> two integers. Is it possible to
> select for every vertex of $G$ exactly
> $b$ different neighbors such that no
> node is chosen more then $c$ times.

The case $b = 1$ can be solved for any $c$ in polynomial time using maximal matching.

Motivation: Each node wants to place $b$ backups at different neighbors, but each node has only capacity to store $c$ backups.

**Tags:** cc.complexity-theory, np-hardness, graph-algorithms


---

## 1 answers

### Answer by username_1 on 2010-11-26. Score: 11 | Accepted answer

I think the following is a polynomial-time algorithm based on maximum flow. Let $G(V,E), b, c$ be the input.

* Construct a directed bipartite graph $H(L,R,F)$ with $L$ and $R$ being the left and right partitions and $F$ being the directed edges *from* $L$ to $R$.
* Let $|V| = n$. There are $n$ vertices in $L$ and $n$ vertices in $R$.
* Each vertex $v \in V$ has a "copy" in $L$ (say $v\_l$) and a copy in $R$ (say $v\_r$).
* If $(u,v) \in E$ add a directed edge from $u\_l$ to $v\_r$. Each such edge has capacity 1.
* Add a "source" node $s$ and add directed edges from $s$ to each vertex in $L$. Each such edge has a capacity $b$.
* Add a "sink" node $t$ and add directed edges from each vertex in $R$ to $t$. Each such edge has a capacity $c$.
* Find maximum flow from $s$ to $t$.

The given graph $G$ has a solution if and only if the max-flow computed above saturates every edge from $s$ to $L$, i.e., the flow on every edge from $s$ to $L$ is equal to $b$.

> **Comments:**
> **username_2**: Indeed, this is precisely the intended solution when I assign this as a homework problem.  

---

