Проблема резервного копирования NP-завершена?

Является ли следующее решение задачи NP-завершенным:

Пусть неориентированный граф и двумя целыми числами. Можно ли выбрать для каждой вершины ровно разных соседей, чтобы ни один узел не был выбран больше, чем раз.$G$$b \le c$$G$$b$$c$

Случай может быть решен для любого за полиномиальное время с использованием максимального соответствия.$b = 1$$c$

Мотивация: каждый узел хочет разместить резервные копии у разных соседей, но у каждого узла есть только емкость для хранения резервных копий .$b$$c$

Я думаю, что следующий алгоритм полиномиального времени, основанный на максимальном потоке. Пусть будет входом.$G(V,E), b, c$

• Построить направленный двудольный граф с и , являющийся левой и правой перегородки и будучи направленным ребра из до .$H(L,R,F)$$L$$R$$F$ $L$$R$
• Пусть . Есть вершин и вершин .$|V| = n$$n$$L$$n$$R$
• Каждая вершина имеет «копию» в (скажем, ) и копию в (скажем, ).$v \in V$$L$$v_l$$R$$v_r$
• Если добавить направленное ребро из в . Каждый такой край имеет емкость 1.$(u,v) \in E$$u_l$$v_r$
• Добавить «источник» узел и добавить направленные ребра из каждой вершиной в . Каждое такое ребро имеет емкость .$s$$s$$L$$b$
• Добавьте «тонущий» узел и добавьте направленные ребра из каждой вершины в к . Каждый такой край имеет емкость .$t$$R$$t$$c$
• Найти максимальный поток от до .$s$$t$

Данный граф имеет решение тогда и только тогда, когда рассчитанный выше максимальный поток насыщает каждое ребро от до , т.е. поток на каждом ребре от до равен .$G$$s$$L$$s$$L$$b$