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.
Is the backup problem NP-complete?
cc.complexity theory;np hardness;graph algorithms
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$.