графы, где раскраска вершин находится в P, но независимое множество является NP-полным

Существует ли пример класса графов, для которого задача раскраски вершин находится в P, но независимым множеством является задача NP-полна?

Возможно, более общее утверждение (с легким доказательством) состоит в том, что следующая задача уже NP-полна:

Входные данные: граф G, 3-раскраска G, целое число k.

Вопрос: G имеет независимый набор размера k?

Это может быть доказано сокращением от Независимого набора. Заметьте, что если мы возьмем граф G, выберем какое-нибудь ребро и поделим его дважды (т.е. заменим ребро {u, v} на путь u, x, y, v, где x и y имеют степень два), то число независимости G увеличивается ровно на один. (Вы можете добавить ровно одно из x или y к любому множеству, которое было независимым в G, и обратное тоже не сложно.) Таким образом, вопрос о том, имеет ли граф G с m ребрами независимый набор размера k, эквивалентен вопросу имеет ли G ', который является результатом подразделения всех ребер в G дважды, независимый набор размера k + m. Но заметьте, что легко получить 3-раскраску G ', разбив G' на три независимых набора следующим образом: один содержит вершины, которые также были в G, а два других класса содержат ровно один из двух " subdivider» вершины для каждого ребра. Следовательно, эта процедура создает граф G 'с его 3-раскраской, так что вычисление его номера независимости дает вам номер независимости исходного графа G.

Предположительно, справка Уэхары «NP-полные задачи на 3-связном кубическом плоском графе и их приложения» (статья, которую я на самом деле не видел) доказывает, что независимое множество является NP-полным даже для плоских графов без треугольников. Но по теореме Грётша они всегда 3-раскрашиваются, и тестирование на меньшее количество цветов, чем 3, легко на любом графике, поэтому они могут быть оптимально раскрашены в P.

Круг графа имеет свойство противоположное: для них окраска NP полная , но независимая Поставленная задача легко.

Это не новый ответ, а скорее разъяснение первого и простого в получении справочника по твердости НЕЗАВИСИМОГО НАБОРА в кубических планарных графах без треугольников: заметка Оуэна Мерфи, Вычисление независимых множеств в графах с большим обхватом , Дискретная прикладная математика 35 (1992) 167-170 доказывает, что

$n$$cn^k$$c>0$$k, 0\le k < 1$

$c$$c>0$

Редукция, обозначенная @BartJansen, является частным случаем в доказательстве Мерфи его теоремы.

Для противоположного свойства линейные графики кажутся более естественными, чем круговые, как рассматривает @DavidEppstein. Для линейных графиков COLORING является NP-полной, но НЕЗАВИСИМЫЙ НАБОР прост.