Показано, что минимальное удаление вершин в двудольном графе является NP-полным

Рассмотрим следующую проблему, входной экземпляр которой представляет собой простой граф и натуральное целое число . $G$ $k$

Существует ли множество такое, что двудольный и ? $S \subseteq V(G)$ $G - S$ $|S| \leq k$

Я хотел бы показать, что эта проблема является -завершенной, уменьшив к ней 3-SAT, -CLIQUE, -DOMINATING SET или -VERTEX COVER. $\rm{NP}$ $k$ $k$ $k$

Я считаю, что могу свести к этому проблему 3-ЦВЕТА, поэтому мне нужно только посмотреть, как свести к ней одну из упомянутых проблем. Но так как это было бы довольно грязно, мне интересно, увидит ли кто-нибудь элегантное сокращение вышеупомянутых проблем.

Кроме того, есть ли название для решения этой проблемы?

complexity-theory np-complete reductions Jernej
источник

Нечетное прохождение цикла .

Пол GD

Это похоже на набор вершин обратной связи . То есть вы хотите найти минимальное подмножество вершин для удаления так, чтобы полученный граф был ациклическим. Ациклический граф по определению является деревом (или лесом), который является двудольным.

Николас Манкузо

@NicholasMancuso Это не так похоже. Это действительно, как я уже сказал выше, проблема трансверсального нечетного цикла. Или, как указывает Вор, Яннакакис в 70-х и 80-х называл удаление двудольных узлов (или вершин).

Пол GD

@ PålGD, я согласен. Я чувствовал, что самое легкое сокращение будет от FVS. Однако это становится ненужным благодаря его определению как трансверсаль нечетного цикла.

Николас Манкузо

@Jernej: вы говорите: «... Я хотел бы показать, что эта проблема в NP , уменьшив ее до 3-SAT, k-CLIQUE, ...». Вы имеете в виду «Я хотел бы показать, что эта проблема является NP-сложной, используя сокращение от 3-SAT, k-CLIQUE, ...»? (проблема явно в NP, потому что тестирование двудольного графа может быть выполнено за линейное время)

Vor

Ответы:

Ваша проблема - это особый случай более широкого класса проблем, называемых проблемами удаления узлов :

Дж. М. Льюис и М. Яннакакис, «Проблема удаления узлов для наследственных свойств является NP-полной»

$\Pi$ $G$ $\Pi$ $\Pi$ $\Pi$ $\Pi$ $\Pi$ $\Pi$

Ваша проблема - это проблема удаления узлов из-за двойственности , но (как отметил Pal), сегодня она известна как проблема обхода нечетного цикла (OCT).

РЕДАКТИРОВАТЬ

Что касается прямого сокращения, я подумал об этом из 3SAT.

$n$ $m$ $x_i, \overline{x_i}$ $n+1$ $x_i$ $x_i$ $\overline{x_i}$ $n$ $x_i$ $\overline{x_i}$ $C_j$ $C_j$

$G$ $n$

введите описание изображения здесь

Вор
источник

Это не совсем тот ответ, который задает вопрос. ОП хотят явно сократить, используя данную проблему. Кроме того, проблема известна сегодня как трансверсаль нечетного цикла.

Пол GD

@ PålGD: ты прав.

Vor

Да, но я не могу сразу увидеть сокращение из списка проблем ОП, хотя ... Я знаю только то, что вы упомянули, от Яннакакиса.

Пол GD

@ PålGD: я подумаю о другом сокращении, но, если честно, я не уверен, чего именно хочет ОП (см. Мой комментарий выше).

Vor

@Vor То, что я хочу, это увидеть простое сокращение до одной из упомянутых проблем. Эта статья мне известна, но я скорее ищу самое прямое сокращение.

Jernej