Гамильтоновость k-регулярных графов

24

Известно, что он является NP-полным, чтобы проверить, существует ли гамильтонов цикл в 3-регулярном графе, даже если он плоский (Гэри, Джонсон и Тарьян, SIAM J. Comput. 1976) или двудольный (Akiyama, Nishizeki, и Saito, J. Inform. Proc. 1980), или чтобы проверить, существует ли гамильтонов цикл в 4-регулярном графе, даже если это граф, образованный расположением кривых Жордана (Iwamoto and Toussaint, IPL 1994).

Для какого другого k известно, что он NP-полон, чтобы проверить гамильтоновость k-регулярных графов?

Частный случай, который меня интересует, - это 6-регулярные графы с дополнительным условием, чтобы граф имел нечетное количество вершин. Если бы этот случай мог быть показан как NP-полный (или полиномиальный), это оказало бы влияние на проблему рисования графика, описанную в http://arxiv.org/abs/1009.0579 . Условие «нечетное число вершин» заключается в том, что для 6-регулярных графов я действительно хочу знать, содержит ли граф гамильтонов цикл или двудольный 2-фактор; но наличие нечетного числа вершин исключает возможность двудольного 2-фактора, оставляя только возможность гамильтонова цикла.

Дэвид Эппштейн
источник

Ответы:

15

Первый шаг. Предположим, что граф имеет четное число вершин. На втором этапе мы расширим конструкцию, так что если k четное, то мы покажем, как превратить граф в нечетное число вершин.

Решение является уточнением идеи, предложенной в другом ответе.

Первая часть

Утверждение: для регулярного графа G с четным числом вершин можно вычислить граф H, который является ( k + 1 ) -регулярным, и H гамильтонов, если G гамильтониан.kGH(k+1)HG

Доказательство: возьмем две копии регулярного графа G , назовем их G 1 и G 2 . Для вершины v V ( G ) пусть v 1 и v 2 - соответствующие копии. Создайте клику с k + 2 вершинами для v . Выберите в этой клике две вершины v и v и удалите ребро между ними. Затем подключите v 1 к v и v 2kGG1G2vV(G)v1v2k+2vvvv1vv2к . Пусть C ( v ) обозначает этот компонент для v .vC(v)v

Повторите это для всех вершин графа , и пусть H обозначает результирующий граф.GH

Ясно, что граф является k + 1 регулярным. Мы утверждаем, что H гамильтонова тогда и только тогда, когда G гамильтонова.Hk+1HG

Одно направление ясно. Учитывая Hambiltonian цикл в , мы можем перевести его в цикл в H . Действительно, всякий раз, когда цикл посещает вершину vGHv , мы интерпретируем ее как перемещение от к v 2 (или наоборот), посещая все вершины в C ( v ) . Таким образом , это приводит к гамильтонова цикла в H . (Обратите внимание, что именно здесь мы используем тот факт, что исходное количество вершин четное - если цикл нечетный, это ломается.)v1v2C(v)H

Что касается другого направления, рассмотрим гамильтонов цикл в . Должно быть, что C ( v ) посещается частью цикла, который начинается в v 1 , посещает все вершины C ( v ) и уходит из v 2 (или симметричного варианта). Действительно, гамильтонов цикл не может входить и выходить из одного и того же v i . Таким образом , гамильтонов цикл в H в качестве естественного интерпретации как гамильтонова цикла в G . QED.HC(v)v1C(v)v2viHG

Вторая часть

Как отмечается ниже, Цуёси, любой 3-регулярный граф имеет четное число вершин. Таким образом, задача сложна для регулярного графа с четным числом вершин. А именно, приведенное выше сокращение показывает, что проблема трудна для любого k -регулярного графа, хотя полученный граф имеет четное число вершин.3k

Заметим, что это подразумевает, что следующая проблема NP-трудна.

Задача A: Решить, имеет ли k-регулярный граф с четным числом вершин гамильтонов цикл, проходящий через конкретное ребро e .Ge

Однако, если даже тогда дано ( G , e ), мы можем свести его к желаемой проблеме. Действительно, мы заменяем ребро e на клику из k + 1 вершин, как перед удалением одного ребра в клике и соединением двух его конечных точек с конечными точками e и удалением e из графа. Понятно, что для нового графа H :k(G,e)ek+1eeH

  • является к -регулярной.Hk
  • гамильтониан тогда и только тогда, когда G гамильтониан с циклом, использующим e .HGe
  • имеет | V ( G ) | + k + 1 вершин => H имеет нечетное количество вершин.H|V(G)|+k+1H

Обратите внимание, что регулярный граф для k нечетного должен иметь четное количество вершин (просто посчитать ребра). Таким образом, не существует k- регулярных графов с нечетным числом вершин, где k нечетно.kkkk


Результат

Трудно определить, имеет ли регулярный граф гамильтонов цикл для k 3 . Проблема остается NP-Hard, даже если граф имеет нечетное количество вершин.kk3


Конечно, всегда возможно, что я совершил какую-то глупую ошибку ...


Упражнение

Если мы хотим перейти от графа, который является регулярным, к графу, который, скажем, является 2 k -регулярным, то граф, полученный в результате применения приведенного выше сокращения, многократно приводит к графу с размером, который экспоненциально зависит от k . Покажите, что при заданном k -регулярном графе G и i > 2 можно построить граф H, который является ( k + i ) -регулярным и его размер полиномиален по k , ik2kkkGi>2H(k+i)k,i и , где n - количество вершин из G . Более того,nnG гамильтонова тогда и только тогда, когда H гамильтонова.GH

(Я публикую это как упражнение, а не вопрос, поскольку знаю, как это решить.)

Сариэль Хар-Пелед
источник
1
Большой! Я думаю, что этот ответ фактически разрешает первый вопрос: «Для каких других k известно, что он NP-полон, чтобы проверить гамильтоновость k-регулярных графов?», Потому что 3-регулярные графы имеют четное число вершин, и граф H, созданный этим преобразованием, также имеет четное число вершин, если G имеет четное количество вершин.
Цуёси Ито
Но если я не ошибаюсь, тот же контрпример к доказательству Робина является контрпримером к этому доказательству. Пусть G - путь на 2 вершинах. Тогда процедура здесь создает H, который является 9-циклом, который является гамильтоновым.
Эмиль
Как я сказал в отношении ответа Робина, проблема в том, что когда вы пытаетесь «спроецировать» цикл Гамильтона с H на G, цикл может оказаться не циклом, потому что он восстанавливает то, где он был.
Эмиль
@ Эмиль: Я думаю, что путь на 2 вершинах - это действительно особый случай, потому что он имеет гамильтонову цепь, если нам разрешено использовать одно и то же ребро более одного раза.
Цуёси Ито
1
@Sariel Har-Peled: В каждом графе число нечетных вершин (т.е. вершин нечетной степени) является четным. Следовательно, все 3-регулярные графы имеют четное число вершин. Я написал излишне сложный аргумент, не осознавая этого в первой версии комментария (который я изменил менее чем за 5 минут), поэтому извините, если вы прочитали мой старый комментарий и были смущены им.
Цуёси Ито
1

РЕДАКТИРОВАТЬ: Это доказательство неверно, как указано в комментариях. (Должен ли я удалить сообщение?)

Интуитивно кажется, что если гамильтоновость NP-трудна для k-регулярных графов, то она также должна быть NP-трудна для (k + 1) -регулярных графов. Вот сокращение «обратно за конверт», которое мне подходит, но, конечно, может быть и ошибка.

Пусть G k-регулярный граф. Пусть G 'графово декартово произведение G и ребро. Другими словами, G '- это граф, имеющий две копии G, и каждая вершина связана с его копией. G 'теперь (k + 1) регулярно, так как каждая вершина получила 1 дополнительное ребро.

Утверждение: G имеет гамильтонов цикл, если и только если G 'имеет гамильтонов цикл.

Доказательство: если G имеет гамильтонов цикл, легко видеть, что G тоже имеет его. Скажем, (u, v) - ребро в гамильтоновом цикле. Пройдите цикл от u до v без использования этого ребра, и теперь вместо использования ребра перейдите к v 'из v, где v' - это вершина, соответствующая v в копии G. Теперь перейдите цикл в обратном порядке. на этом графике, который вернет нас к вам. Теперь перейдите от u к u, что завершает цикл.

Если G 'имеет гамильтонов цикл, начинающийся с вершины u, рассмотрим одну и ту же последовательность обходов на G. Каждый раз, когда выполняется перемещение к смежной вершине в том же графе, мы делаем одно и то же движение в G. Каждый раз, когда выполняется движение до соответствующей вершины в другом графе мы ничего не делаем. Поскольку каждое движение верно на графе G и цикл заканчивается в вершине u, это гамильтонов цикл.

Робин Котари
источник
1
Я не вижу, как работает второй абзац доказательства. Если мы отбрасываем условие, что G k-регулярна, то, если G - путь, можно привести контрпример к утверждению, что если G ′ гамильтониан, то G также гамильтониан.
Цуёси Ито
1
Я немного обеспокоен последним абзацем здесь. Когда цикл Гамильтона для G 'проецируется (если это правильное слово!) На G, у нас может возникнуть ситуация, когда цикл повторяет свои шаги.
Эмиль
@Tsuyoshi: у вас есть контрпример: просто выберите обычный путь - путь с двумя вершинами.
Эмиль
@ Цуйоши: Ты прав. Доказательство неверно. Должен ли я удалить ответ? У нас есть политика по этому поводу?
Робин Котари
@ Робин, я думаю, что ваш пост должен быть оставлен сейчас, поскольку он вызвал некоторое обсуждение. Это, безусловно, показывает, что это неловкая проблема.
Эмиль