Если вы подразумеваете, что ребра являются «взаимоисключающими», что они не разделяют вершину, то описанная вами проблема является подмножеством общей проблемы Идеальное соответствие в двудольном графе .
Также попробуйте конкретизировать c с терминами P и NP. P является подмножеством NP. Поэтому задача Perfect Matching в двудольном графе также есть в NP, потому что она есть в P. Нечто иное, что вы, возможно, имели в виду, это NP-hardness . По сути, это означает «по крайней мере так же сложно, как каждая проблема в NP».
Таким образом, ваш вопрос должен звучать так: «Есть ли проблема в P?», Потому что, если бы у нас было решение, мы могли бы легко его проверить, таким образом это в NP. Свойство, которое мы можем проверить за полиномиальное время, на самом деле является определением NP .
И, как я уже сказал, из моего понимания ваша проблема является лишь подмножеством проблемы, поэтому также в П.