Le problème de sauvegarde est-il NP-complet?

Le problème de décision suivant est-il NP-complet:

Soit un graphe non orienté et deux entiers. Est-il possible de sélectionner pour chaque sommet de exactement voisins différents de sorte qu'aucun nœud ne soit choisi plus de fois.$G$$b \le c$$G$$b$$c$

Le cas peut être résolu pour tout en temps polynomial en utilisant l'appariement maximal.$b = 1$$c$

Motivation: chaque nœud veut placer sauvegardes chez différents voisins, mais chaque nœud n'a que la capacité de stocker sauvegardes.$b$$c$

Je pense que ce qui suit est un algorithme polynomial basé sur le débit maximum. Soit l'entrée.$G(V,E), b, c$

• Construire un graphe biparti dirigé avec et étant les cloisons gauche et droite et étant les bords dirigés de à .$H(L,R,F)$$L$$R$$F$ $L$$R$
• Soit . Il y a sommets et sommets .$|V| = n$$n$n $L$$n$$R$
• Chaque sommet a une "copie" dans (disons ) et une copie dans (disons ).L v l R v $v \in V$$L$$v_l$$R$$v_r$
• Si ajoutez un bord dirigé de à . Chacun de ces bords a la capacité 1.u l v $(u,v) \in E$$u_l$$v_r$
• Ajouter une « source » noeud et ajouter des bords dirigés de à chaque sommet dans . Chacun de ces bords a une capacité .s L $s$$s$$L$$b$
• Ajoutez un nœud "puits" et ajoutez des arêtes dirigées de chaque sommet de à . Chacun de ces bords a une capacité .R t $t$$R$$t$$c$
• Trouvez le débit maximal de à .$s$$t$

Le graphe donné a une solution si et seulement si le débit maximum calculé ci-dessus sature chaque bord de à , c'est-à-dire que le débit sur chaque bord de à est égal à .s L s L $G$$s$$L$$s$$L$$b$