Czy problem tworzenia kopii zapasowej NP jest kompletny?

Czy następujący problem decyzyjny NP-zupełny:

Niech będzie nieukierowanym wykresem i dwiema liczbami całkowitymi. Czy można wybrać dla każdego wierzchołka dokładnie różnych sąsiadów, tak że żaden węzeł nie zostanie wybrany więcej niż razy.$G$$b \le c$$G$$b$$c$

Przypadek można rozwiązać dla dowolnego czasie wielomianowym, stosując maksymalne dopasowanie.$b = 1$$c$

Motywacja: każdy węzeł chce umieszczać kopie zapasowe u różnych sąsiadów, ale każdy węzeł ma tylko pojemność do przechowywania kopii zapasowych .$b$$c$

Myślę, że poniżej jest algorytm wielomianowy oparty na maksymalnym przepływie. Niech będą danymi wejściowymi.$G(V,E), b, c$

• Skonstruować skierowaną dwustronnego wykres z i , będących w lewo i w prawo przegrody i są składnikami skierowane krawędzie od do .$H(L,R,F)$$L$$R$$F$ $L$$R$
• Niech . Istnieje wierzchołki i wierzchołki .$|V| = n$$n$$L$$n$$R$
• Każdy wierzchołek ma „kopię” w (powiedz ) i kopię w (powiedz ).$v \in V$$L$$v_l$$R$$v_r$
• Jeśli dodaj skierowaną krawędź od do . Każda taka krawędź ma pojemność 1.$(u,v) \in E$$u_l$$v_r$
• Dodać węzeł „source” i dodać skierowane krawędzie z na każdym wierzchołku w . Każda taka krawędź ma pojemność .$s$$s$$L$$b$
• Dodaj węzeł „zatapiania” i dodaj skierowane krawędzie z każdego wierzchołka od do . Każda taka krawędź ma pojemność .$t$$R$$t$$c$
• Znajdź maksymalny przepływ od do .$s$$t$

Dany wykres ma rozwiązanie wtedy i tylko wtedy, gdy obliczony powyżej maksymalny przepływ nasyca każdą krawędź od do , tj. Przepływ na każdej krawędzi od do jest równy .$G$$s$$L$$s$$L$$b$