Ist das Backup-Problem NP-vollständig?

Ist das folgende Entscheidungsproblem NP-vollständig:

Sei ein ungerichteter Graph und b ≤ c zwei ganze Zahlen. Ist es möglich, für jeden Scheitelpunkt von G genau b verschiedene Nachbarn auszuwählen, so dass kein Knoten mehr als c- mal ausgewählt wird.$G$$b \le c$$G$$b$$c$

Der Fall kann für jedes c in Polynomzeit unter Verwendung maximaler Übereinstimmung gelöst werden .$b = 1$$c$

Motivation: Jeder Knoten möchte Backups bei verschiedenen Nachbarn platzieren, aber jeder Knoten kann nur c Backups speichern .$b$$c$

Ich denke, das Folgende ist ein Polynom-Zeit-Algorithmus, der auf maximalem Fluss basiert. Sei die Eingabe.$G(V,E), b, c$

• Konstruieren Sie einen gerichteten zweigliedrigen Graphen wobei L und R die linken und rechten Partitionen und F die gerichteten Kanten von L nach R sind .$H(L,R,F)$$L$$R$$F$ $L$$R$
• Lassen Sie . Es gibt n Ecken in L und n Ecken in R .$|V| = n$$n$$L$$n$$R$
• Jeder Scheitelpunkt hat eine "Kopie" in L (sagen wir v l ) und eine Kopie in R (sagen wir v r ).$v \in V$$L$$v_l$$R$$v_r$
• Wenn füge eine gerichtete Kante von u l zu v r hinzu . Jede solche Kante hat die Kapazität 1.$(u,v) \in E$$u_l$$v_r$
• Fügen Sie einen "Quell" -Knoten und fügen Sie jedem Scheitelpunkt in L gerichtete Kanten von s hinzu . Jede solche Kante hat eine Kapazität b .$s$$s$$L$$b$
• Fügen Sie einen "Senken" -Knoten und fügen Sie gerichtete Kanten von jedem Scheitelpunkt in R zu t hinzu . Jede solche Kante hat eine Kapazität c .$t$$R$$t$$c$
• Finden Sie den maximalen Durchfluss von nach t .$s$$t$

Der gegebene Graph hat genau dann eine Lösung, wenn der oben berechnete Maximalfluss jede Kante von s nach L sättigt , dh der Fluss an jeder Kante von s nach L ist gleich b .$G$$s$$L$$s$$L$$b$