Частично окрашивание графа с 1 цветом

Question

Я только начал читать теорию графов и читал о раскраске графа. Эта проблема возникла у меня в голове:

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

Мой подход: сначала мы делим график на изолированные компоненты и делаем это для каждого компонента. Мы делаем ДФС дерево и сделать 2 дп массива при обходе его так, чтобы корневая последний приходит:

dp[0][u]=sum(dp[1][visited children])

dp[1][u]=sum(dp[0][visited children])

ans=max(dp[1][root],dp[0][root])

dp[0][i] , dp[1][i] are initialized to 0,1 respectively.

Здесь 0 означает неокрашенный и 1 означает, цвета.

Но это не работает для циклических графов, так как я предположил, что ни один из посещенных детей не подключен.

Может ли кто-нибудь вести меня в правильном направлении, как решить эту проблему для циклических графиков (а не грубой силой)? Возможно ли изменить мой подход или нам нужно разработать другой подход? Будет ли жадный подход, например, окрашивать узлы с наименьшими ребрами?

Answer 1

Эта проблема также NP-Hard и известна как maximum independent set problem.

Множество S<=V называется независимый набор в графе, если для каждого из двух вершин u,v в S, нет края (u,v).

Максимальный размер S (это номер, который вы ищите) называется номером независимости, и, к сожалению, найти его NP-Hard.

Итак, если P = NP, ваш алгоритм не подходит для графиков общего назначения.

---

Доказывая это довольно просто, учитывая график G=(V,E), создать дополнительный граф G'=(V,E') где (u,v) находится в E' тогда и только тогда, когда (u,v) НЕ в E.

В настоящее время, учитывая график G, есть клика размера k тогда и только тогда, когда существует независимый набор размера k в G', используя те же самые вершины (так как, если (U, V) являются две вершинами независимыми set, нет края (u,v) в E', и по определению есть ребро в E. Повторите для всех вершин в независимом наборе, и вы получили клику в G).

С clique problem NP-Hard, это делает его одним из таких, как хорошо.