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