# Is the backup problem NP-complete?

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.

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

• Indeed, this is precisely the intended solution when I assign this as a homework problem. – Jeffε Nov 27 '10 at 7:00