Ссылка для NP-твердости 3-х цветов?

33

У меня есть исторический вопрос.

Я пытаюсь определить ссылку на тот факт, что 3-окрашиваемость графиков (альтернативно, окрашиваемость для заданного k \ geq 3 ) является NP-трудной.КК3

Заманчивым ответом является «оригинальная статья Карпа», но это не так. Вот сканирование: сводимость среди комбинаторных проблем, Карп (1972) . Это доказывает, что хроматическое число (вход: граф. Выход: χ(г) ) является сложным. Это более сложная проблема, и сокращение отличается от стандартной конструкции гаджета (с 3 цветами: True, False и Ground), которая подразумевает твердость 3-цветности.

Garey and Johnson, Computer and intractability , имеют К окрашиваемость как [GT4] и ссылаются на Karp (1972).

Тор Хусфельдт
источник
На странице 84 Гэри и Джонсон утверждают, что 3-цветность является NP-полной, цитируя статью Стокмейера, представленную в ответе Юрия. В теореме 4.2 они также предоставляют более простое доказательство результата Стокмейера.
Тайсон Уильямс

Ответы:

44

László Lovász , « Покрытия и раскраски гиперграфов» , Материалы четвертой Юго-Восточной конференции по комбинаторике, теории графов и вычислительной технике, Utilitas Math., Winnipeg, Man., 1973, pp. 3–12, доказали, что хроматическое число уменьшается до 3- colourability.

Я думаю, что это первое доказательство NP-полноты 3-окрашиваемости.

Вот бумага Ловаша; см. также превосходное объяснение Вашека Чваталя сокращению Ловаша.

VB Le
источник
21

Вот еще одна статья 1973 года, которая доказывает, что 3-цветность NP-трудна.

Ларри Дж. Стокмейер. «Плоская 3-цветность полиномиальна». ACM SIGACT News, vol. 5, нет 3, 1973.

(Похоже, что Ловаш и Стокмейер получили свои результаты независимо друг от друга.)

Обновление: см. Комментарии ниже.

Юрий
источник
5
Если я не ошибаюсь, Stockmeyer не доказал NP-твердость 3-Coloring в этой статье. Там он переводит 3-раскраски в плоскую 3-раскраску и передает твердость 3-раскраски Карпу (1972). Это неправильно, как указал Тор Хусфельдт.
user13136
2
Понимаю. Спасибо user13136! К сожалению, у меня нет доступа к этой статье сейчас. Я видел только реферат этой статьи и ссылки на нее.
Юрий
4
Теперь я видел бумагу Стокмейера через цифровую библиотеку ACM, и она включает в себя полное доказательство твердости 3-цветности. (Сокращение от 3-удовлетворенности.) Таким образом, кажется, что первоначальное утверждение Юрия в конце концов является правильным, и Стокмейер и Ловош получили результат независимо (и с использованием различных сокращений.)
Тор Хусфельдт
3
Ой! Я не знал, что может быть назначена только одна галочка. Ответ Stockmeyer правильный, поэтому я механически нажал на галочку. Что мне делать, разрываясь между двумя взаимоисключающими версиями истины?
Thore Husfeldt
2
О, мне было просто любопытно, потому что я нахожу бумагу Ловаша довольно красивой. Я не хотел обесценивать ответ Юрия и не думал, что vb le очень разбит этим;)
user13136