9
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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

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

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.