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

23

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

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

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

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

Учитывая G,k , мы знаем , что G¯ может быть nk+1 -colored с k вершинами все цветные Правда тогда и только тогда G имеет k -clique. Назовем исходные вершины G v1,,vn а затем добавим к G¯ дополнительные вершины: Cij с 1in , 0jk, Ключевым инвариантом будет то, что Cij может быть окрашен в True, если и только если среди вершин {v1,,vi} есть хотя бы j вершин, окрашенных в True. Итак, каждый Ci0 может быть True. Тогда Cij при j>0 получает цвет C(i1)jC(i1)(j1)vi где все ненастоящие цвета считаются ложными. Существуетk -клика вG еслиCnk может быть окрашен в True, поэтому, если мы навязываем эту раскраску, новый граф раскрашивается, еслив исходном графебылаk -клика.

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

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

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

Уильям Макрэй
источник
4
Вид прямого сокращения, который вы ищете, может быть трудным найти, так как клика и раскраска в некотором роде противоположны в том смысле, что найти 1-клику так же легко, как и n-раскраску. Поэтому, возможно, сокращение должно иметь вид: имеет n - k- раскраску тогда и только тогда, когда G имеет k -кликGnkGk
Мартин Ватшелле
Я согласен, что это сложно; это причина моего интереса; Я подробно расскажу о мотивации в этом вопросе. -раскраске идеи уже получила мне ближе всего . Если есть к -clique в G тогда ¯ G может иметь все вершины в клике Monochromatic , поскольку они являются независимым множеством. Проблема в том, что хроматическое число остальных может варьироваться. Связывание двух вершин с K n - k - 1 заставляет их иметь одинаковый цвет, но я понятия не имею, какой набор вершин использовать. Гаджет , что силы некоторые I из JnkkGG¯Knk1ijвершины, которые будут однотонными, сделают это.
Уильям Макрэй
3
Я согласен с Мартином в том, что это может быть даже невозможно (без прохождения, скажем, 3SAT). Клика и окраска имеют очень мало общего. Поэтому я хочу напомнить теорему Эрдеша, учитывая натуральные значения g и k, есть граф с обхватом не менее g и хроматическим числом не менее k (подумайте об этом некоторое время, если вы с ним не знакомы). Наконец, ваше сокращение также должно учитывать, что хотя Clique (и Independent Set) находится в параметризованном набором решений, эквивалентная параметризация для хроматического числа графа отсутствует. W[1]
Пол GD
Я не понимаю комментарий @ MartinVatshelle. Насколько я знаю, все 1-клика, 1-раскраска, n-клика и n-раскраска тривиальны на одном уровне. (не думайте, что вы всегда можете ответить на 1-клику ДА: входной график может быть пустым!)
Иксинь Цао
Я думаю, что точка зрения Мартина в том, что это шоу и χ ( G ) = 3 , но найти К 4 труднее, чем К 3 . Так что в этих двух концепциях есть немного двойственности. Замечание @ PålGD о теореме Эрдёша является отличным (и я люблю эту теорему), поскольку графы с большим обхватом имеют большое число независимости, и поэтому их обратные вычисления будут иметь большие клики. В целом он чувствует, что это ловушка , хотя здесь, что связать кликами и Красители в одних и тех же или подобных графиков, но , как и в обратном направлении сокращения может построить совсем другой график , чем G .χ(G)=4χ(G)=3K4K3G
Уильям Макрэй

Ответы:

14

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

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

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

{x,y,z}Hy=(v,i)z=(u,j)uvi=juvGn H x y z x y z y x z z x y max(i,j)knH, В этой клике выберите три вершины , и . Соедините с каждой вершиной в клике, кроме и ; соединить с каждой вершиной клики, кроме и ; и соедините с каждой вершиной в клике, кроме и .xyzxyzyxzzxy

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

Дэвид Эппштейн
источник
2
Это замечательно.
Уильям Макрэй
По некоторым причинам мое редактирование было отклонено, но последнее предложение должно описывать вершины G, а не H (поскольку оно предназначено для описания клики в G). Что-то вроде «Клика в может быть восстановлена ​​из раскраски H, если » Также я забыл скажи спасибо за ответ, это было очень полезно! { v : i k χ ( ( v , i ) ) = χ ( x ) } .G{v:ikχ((v,i))=χ(x)}.
Уильям Макрэй
Конечно, вы могли бы добавить к этому предложению еще один пункт об удалении из каждой пары, но я подумал, что этот шаг достаточно легко пропустить, и у меня общее ощущение, что (когда его можно сохранить достаточно коротким) проза имеет тенденцию быть более читабельным, чем формула. i
Дэвид Эппштейн
Я согласен, что проза предпочтительнее. Может быть, просто добавление фразы типа «первая координата каждого (v, i) ...» является идеей. Причина, по которой я беспокоюсь о технических аспектах, заключается в том, что при первом чтении сокращений может быть трудно точно определить точные определения элементов на первом языке и на втором, и что именно. В тот момент, когда что-то кажется нарушающим определение, оно может бросить меня в тупик. Если бы у меня были проблемы с пониманием предыдущих предложений и я добрался до последнего, я бы определил, что G и H имеют вершины вида (v, i).
Уильям Макрэй
Я должен также сказать, что я думаю, что вы справились с этим сокращением намного лучше, чем почти все другие, которые я читал. В литературе есть проблема, что многие сокращения указаны формально без мотивации или интуиции, и вы очень хорошо избежали этого.
Уильям Макрэй
-7

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

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

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

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

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

ВЗН
источник
5
Используя свойство , вы можете вызвать алгоритм для k - C O L O R A B I L I T Y на G : если алгоритм возвращает Y E S , то G не содержит никаких клика размером не менее k + 1 . Однако обратное утверждение не имеет места: если алгоритм возвращает N O , то G может иметь или не иметь клику размера, по крайней мереχ(G)ω(G)kCOLORABILITYGYESGk+1NOG (в качестве контрпримера рассмотрим пирамиду, полигональное основание которой имеет нечетное число вершин: она не 3 -цветна, но не имеет клики размером не менее 4 ). k+134
Джорджио Камерани,
да, согласился; насколько я понимаю, первоначальный пост не был настойчивым на направлении сокращения, но больше подчеркивал необходимость избегать SAT в качестве посредника, требуя «довольно краткого объяснения». Также, очевидно, никто не упомянул вышеупомянутый фактоид до сих пор .... вопрос и комментарии также, по-видимому, неверно указывают на то, что две проблемы не связаны друг с
другом
1
Извиняюсь, если направление было неоднозначным. Я заинтересован в правильном сокращении (ДАДА), и меня интересует сокращение от Clique до k-Color. У меня есть другое направление, и это объясняется в моем посте. Конечно, есть много вещей, которые связывают клики в графах с раскрасками в графах и наоборот, и действительно, я видел многие из них (и я предполагаю, что многие другие здесь видели много из них), но я действительно заинтересован исключительно в прямой сокращение или убедительное объяснение того, почему оно может не существовать.
Уильям Макрэй
1
@vzn: Мой комментарий не был предназначен для критики вашего ответа. По правде говоря, вначале я сделал рассуждения, аналогичные вашим, но затем я понял, что, если бы имел место противоположный смысл, то на общих графах, который, как известно, является NP-полным , можно было бы решить тривиально, просто проверив, имел ли входной граф клику из 4 узлов: любой G был бы 3 -цветным, если и только если бы он не содержал клику размера 4 (это, конечно, просто ложь, так как контрпример пирамиды показывает). Кстати: я не тот, кто отрицал. 3COLORING4G34
Джорджио Камерани
3
@WilliamMacrae: Было совершенно ясно, что вы хотите сокращение на , иначе это не было бы сокращением! Кроме того, было совершенно ясно, что вы хотели сократить с C L I Q U E до C O L O R I N G, а не наоборот. CLIQUECOLORING
Джорджио Камерани