Натуральная КЛИК к уменьшению k-цвета

Ясно, что сокращение от CLIQUE до k-Color, потому что они оба NP-Complete. Фактически, я могу построить один, составив сокращение от CLIQUE до 3-SAT с сокращением от 3-SAT до k-Color. Мне интересно, есть ли разумное прямое сокращение между этими проблемами. Скажем, сокращение, которое я мог бы объяснить другу довольно кратко, без необходимости описывать промежуточный язык, такой как SAT.

В качестве примера того, что я ищу, вот прямое сокращение в обратном направлении: учитывая G с $n$ и некоторым $k$ (количеством цветов), создайте граф G 'с $kn$ вершинами (по одному на цвет на вершину) , Вершины $v'$ , $u'$ соответствующие вершинам $v, u$ и цветам $c, d$ соответственно, смежны тогда и только тогда, когда $v \neq u$ и ( $c \neq d$ или $vu \not \in G$ ). $n$ -clique в $G'$имеет только одну вершину за вершиной в $G$ , и соответствующие цвета являются собственно $k$ -раскраска $G$ . Аналогичным образом , любая собственная $k$ -раскраска $G$ имеет соответствующую клику в $G'$ .

Редактировать : Чтобы добавить некоторую краткую мотивацию, исходные 21 задачи Карпа доказаны как NP-Complete деревом сокращений, где CLIQUE и Chromatic Number образуют корни основных поддеревьев. Есть некоторые естественные сокращения между проблемами в поддереве CLIQUE и поддереве Chromatic Number, но многие из них найти так же сложно, как и ту, о которой я спрашиваю. Я пытаюсь детализировать, показывает ли структура этого дерева некоторую базовую структуру в других проблемах или это полностью следствие того, какие сокращения были обнаружены первыми, поскольку у них меньше мотивации для поиска сокращений между двумя проблемами, когда они как известно, находятся в одном классе сложности. Конечно, порядок оказал некоторое влияние, и части дерева можно переставить, но можно ли их произвольно переставить?

Редактировать 2 : Я продолжаю искать прямое сокращение, но вот набросок наиболее близкого, который я получил (это должно быть действительное сокращение, но имеет CIRCUIT SAT в качестве явного посредника; несколько субъективно, лучше ли это, чем составление двух сокращений, как указано в первом абзаце).

Учитывая $G, k$ , мы знаем , что $\overline{G}$ может быть $n-k+1$ -colored с $k$ вершинами все цветные Правда тогда и только тогда $G$ имеет $k$ -clique. Назовем исходные вершины $G$ $v_1, \ldots, v_n$ а затем добавим к $\overline G$ дополнительные вершины: $C_{ij}$ с $1 \le i \le n$ , $0 \le j \le k$, Ключевым инвариантом будет то, что $C_{ij}$ может быть окрашен в True, если и только если среди вершин $\{v_1,\ldots, v_i\}$ есть хотя бы $j$ вершин, окрашенных в True. Итак, каждый $C_{i0}$ может быть True. Тогда $C_{ij}$ при $j > 0$ получает цвет $C_{(i-1)j} \vee C_{(i-1)(j-1)} \wedge v_i$ где все ненастоящие цвета считаются ложными. Существует$k$ -клика в$G$ если$C_{nk}$ может быть окрашен в True, поэтому, если мы навязываем эту раскраску, новый граф раскрашивается, еслив исходном графебыла$k$ -клика.

Гаджеты AND и OR для обеспечения взаимосвязей очень похожи на сокращение от CIRCUIT SAT до 3-COLOR, но здесь мы включаем $K_{n-k+1}$ в наш граф, выбираем вершины T, F и Ground, а затем соединяем все другие ко всему , но $v_i$ с; это гарантирует, что $C_{ij}$ s и другие гаджеты получают только 3 цвета.

Во всяком случае, часть этого сокращения чувствует прямой, но использование И / ИЛИ ворот гораздо менее прямой. Остается вопрос, есть ли более элегантное сокращение?$\overline G$

Изменить 3 : Было несколько комментариев о том, почему это сокращение будет трудно найти. CLIQUE и k-Color - это действительно разные проблемы. Даже без сокращения ответ, который подробно объясняет, почему сокращение является трудным в одном направлении, но возможно в другом, был бы очень полезным и внес бы большой вклад в проблему.

Учитывая график и число K , такое , что вы хотите знать , является ли G содержит K -clique, пусть п число вершин в G . Построим другой граф H , таким образом, что Н является п -раскрашиваемым тогда и только тогда , когда G имеет K -clique, следующим образом :$G$$k$$G$$k$$G$$H$$H$$n$$G$$k$

(1) Для каждой вершины в G сделайте n- клик вершин ( v , i ) в H , где i находится в диапазоне от 1 до n .$v$$G$$n$$(v,i)$$H$$i$$1$$n$

(2) Добавление одного дополнительные вершины в H .$x$$H$

$\{x,y,z\}$$H$$y=(v,i)$$z=(u,j)$$u\ne v$$i=j$$u$$v$$G$n H x ′ y ′ z ′ x y ′ z ′ y x ′ z ′ z x ′ y $\max(i,j)\le k$$n$$H$, В этой клике выберите три вершины , и . Соедините с каждой вершиной в клике, кроме и ; соединить с каждой вершиной клики, кроме и ; и соедините с каждой вершиной в клике, кроме и .$x'$$y'$$z'$$x$$y'$$z'$$y$$x'$$z'$$z$$x'$$y'$

Эти устройства , добавленные на стадии (3) предотвратить тройки вершин , и от всего отдается тот же цвет, друг с другом в действительной окраске . Клика в может быть восстановлена ​​из раскраски как множества вершин которые находятся в том же цветовом классе, что и и имеют .y z H G H ( v , i ) x i ≤ $x$$y$$z$$H$$G$$H$$(v,i)$$x$$i\le k$

?? раскраска и обнаружение кликов, как известно, в течение десятилетий тесно связаны с помощью теории графов (возможно, даже в 60-е годы?), даже не с помощью SAT в качестве посредника (что стало типичным после доказательства Кука в 1971 году). Полагаю, что существуют алгоритмы, основанные на следующем основном свойстве :

Если G содержит клику размером k, то для окраски этой клики требуется как минимум k цветов; другими словами, хроматическое число - это, по крайней мере, число клики: $\chi(G) \ge \omega(G).\,$

не уверен в точных ссылках, но [1,2] - хорошие места для начала, точный алгоритм или ссылка, по крайней мере, вероятно, упоминается в этих книгах

[1] Клик, окраска и удовлетворенность, 2-й вызов DIMACS

[2] Dimacs vol. 26: клики, окраска и выполнимость