O problema do backup está NP-completo?

O seguinte problema de decisão é NP-completo:

Seja um gráfico não direcionado e dois inteiros. É possível selecionar para cada vértice de exatamente vizinhos diferentes, de modo que nenhum nó seja escolhido mais que vezes.$G$$b \le c$b $G$$b$$c$

O caso pode ser resolvido para qualquer em tempo polinomial usando a correspondência máxima.$b = 1$$c$

Motivação: cada nó deseja colocar backups em vizinhos diferentes, mas cada nó tem apenas capacidade para armazenar backups.$b$$c$

Eu acho que o seguinte é um algoritmo de tempo polinomial baseado no fluxo máximo. Seja a entrada.$G(V,E), b, c$

• Construir um grafo orientado bipartido com e sendo as partições esquerdas e direitas e sendo as arestas dirigidas a partir de a .L R F L $H(L,R,F)$$L$$R$$F$ $L$$R$
• Vamos . Existem vértices e vértices em .n L n $|V| = n$$n$$L$$n$$R$
• Cada vértice possui uma "cópia" em (digamos ) e uma cópia em (digamos ).L v l R v $v \in V$$L$$v_l$$R$$v_r$
• Se adicione uma aresta direcionada de a . Cada uma dessas arestas tem capacidade 1.u l v $(u,v) \in E$$u_l$$v_r$
• Adicionar um nó "fonte" e adicionar bordas dirigidas de para cada vértice em . Cada uma dessas arestas tem capacidade .s L $s$$s$$L$$b$
• Adicione um nó "afundar" adicione arestas direcionadas de cada vértice em a . Cada borda desse tipo tem capacidade .R t $t$$R$$t$$c$
• Encontre o fluxo máximo de a .$s$$t$

O gráfico dado tem uma solução se e somente se o fluxo máximo calculado acima saturar todas as arestas de a , ou seja, o fluxo em todas as arestas de a é igual a .s L s L $G$$s$$L$$s$$L$$b$