¿El problema de copia de seguridad NP-completo?

¿Es el siguiente problema de decisión NP-completo:

Sea un gráfico no dirigido y dos enteros. ¿Es posible seleccionar para cada vértice de exactamente vecinos diferentes de modo que no se elija ningún nodo más de veces?b ≤ c G b $G$$b \le c$$G$$b$$c$

El caso se puede resolver para cualquier en tiempo polinomial utilizando la coincidencia máxima.$b = 1$$c$

Motivación: cada nodo quiere colocar copias de seguridad en vecinos diferentes, pero cada nodo solo tiene capacidad para almacenar copias de seguridad .$b$$c$

Creo que el siguiente es un algoritmo de tiempo polinómico basado en el flujo máximo. Sea la entrada.$G(V,E), b, c$

• Construir un gráfico bipartito dirigido con L y R siendo las particiones izquierda y derecha y F siendo los bordes dirigidos de L a R .$H(L,R,F)$$L$$R$$F$ $L$$R$
• Dejar . Hay n vértices en L y n vértices en R .$|V| = n$$n$$L$$n$$R$
• Cada vértice tiene una "copia" en L (digamos v l ) y una copia en R (digamos v r ).$v \in V$$L$$v_l$$R$$v_r$
• Si agregue un borde dirigido de u l a v r . Cada borde tiene capacidad 1.$(u,v) \in E$$u_l$$v_r$
• Añadir un nodo "fuente" y añadir bordes dirigidos desde s a cada vértice en L . Cada borde tiene una capacidad b .$s$$s$$L$$b$
• Agregue un nodo "sumidero" y agregue bordes dirigidos desde cada vértice en R a t . Cada borde tiene una capacidad c .$t$$R$$t$$c$
• Encontrar el máximo flujo de a t .$s$$t$

El gráfico dado tiene una solución si y sólo si el máximo de flujo calcula anteriormente se satura cada borde de s a L , es decir, el flujo en cada borde de s a L es igual a b .$G$$s$$L$$s$$L$$b$