Самый длинный цикл состоит из двух циклов

Является ли следующая задача NP-полной? (Я предполагаю, что да).

Входные данные: - неориентированный граф, в котором множество ребер можно разложить на два простых цикла, не пересекающих ребра (они не являются частью входных данных). $k \in \mathbb{N},G=(V,E)$

Вопрос: существует ли простой цикл в с длиной больше ? $G$ $k$

Очевидно, что проблема в NP, и максимальная степень в равна , но это, похоже, не помогает. $G$ $\leq 4$

graph-theory np-complete decision-problem Листинг
источник

Я не думаю, что вы правы насчет "не более 4 путей, соединяющих любую пару". См .: i.imgur.com/mYL4n1V.png

svinja

@svinja Вы правы, я должен был сказать, что между любой парой из двух вершин существует не более 4 парных непересекающихся путей.

Объявление

Ваш заголовок вводит в заблуждение, потому что самый длинный простой цикл не может быть ни одним из двух циклов в разложении

(в любом разложении).

E

$E$

Денис

@dkuper это может на самом деле, посмотрите на объединение двух вершин непересекающихся простых циклов.

Листинг

Моя точка зрения не в том, что он никогда не может быть одним из них, а в том, что иногда это не один из них. Так что проблема не в том, чтобы найти большее из двух.

Денис

Ответы:

Попытка сокращения ....

Сокращение от гамильтонова пути на орграфе с максимальной степенью 3, которое является NPC [G & J] $G = (V,E)$

игнорировать направление ребер и, используя первое сканирование глубины (ненаправленное) от произвольного узла, разделить ребра на два набора отличных (ненаправленных) путей (красный и зеленый на рисунках); $G$
соедините красные пути, добавив дополнительные «связывающие узлы» (фиолетовые узлы на рисунке B) и сделайте неориентированный красный контур; соедините зеленые пути, добавив дополнительные «связывающие узлы» (фиолетовые узлы на рисунке) и сделайте неориентированный зеленый контур;
преобразовать каждый исходный узел из степени 1 и степени 2 (рисунок C), добавив желтых узлов на входящий красный край $b \in V$ $k$ и добавив желтых узлов на первый исходящийкрасныйкрай ; наконец, добавьте желтых узлов «по направлению» ко второму исходящемузеленомукраю используя «обернутый» путь вокруг который касается крайних желтых узлов красных краев (рисунок D). $a\to b$ $k$ $b \to c$ $k$ $b \to d$ $b$

В полученном графике все желтые узлы могут перемещаться с помощью простого пути только в двух направлениях показали на рисунке E и F, фигуры , которые соответствуют двум действительным прохождений исходного узла ; неформально , если ребро к EXTRA «связывая» фиолетовый узел используется, - желтые узлы не могут перемещаться. $3k$ $b \in V$ $k$

преобразовать каждый оригинальный узел V от 2 и полустепени захода полустепени 1 аналогичным образом

Подбор достаточно большой , граф результатов $k \gg |V|$ $G'$ есть простой путь длины больше тогда и только тогда, когда исходный граф имеет гамильтонов путь (длины ) $3k(|V|-1)$ $G$ $|V|-1$

введите описание изображения здесь

Большую картину можно скачать здесь

Вор
источник

Это очень красивое доказательство, может быть, вам следует направить края на рисунке «А», чтобы было легче понять, как получить пути (хотя я думаю, что я это понял).

Листинг

@Listing: строительство путей не зависит от ориентированных ребер ( на самом деле я написал «неориентированный» поиск в ответе). Вы должны начать с произвольного узла, сначала выполнить сканирование по глубине, раскрасив его красными пройденными краями, затем вернуться к первому обнаруженному узлу степени 3 и продолжить сначала сканирование по глубине, покрасив его зелеными пройденными ребрами, и так далее. .. возможно, имеет более формальное определение, но он не приходит на ум прямо сейчас. Дайте мне знать, если вам нужна дополнительная информация.

Вор

Я вижу, свойство, по которому ребра проходят в «правильном» направлении, обеспечивается последним преобразованием. Спасибо за разъяснение.

Объявление

Вдохновленный ответом Вора, я хочу дать более простой.

Начнем с задачи о гамильтоновом цикле для задачи сеточных графов, которая была доказана Итаем.

Легко видеть, что множество ребер графа сетки можно разбить на 2 непересекающихся подмножества: горизонтальное и вертикальное.

Итак, теперь нам нужно сплести все горизонтальные в один простой цикл, а все вертикальные - в другой простой цикл.

Это очень простая задача: для вертикальных разверните от крайнего левого до крайнего правого положения, просто соедините все вертикальные промежутки, затем соедините последовательную вертикальную линию, скоординированную по X, затем соедините самую нижнюю левую вершину с самой высокой правой вершиной. Сделайте аналогично для горизонтальных краев.

Обратите внимание, что полученный граф все еще прост, неориентирован и удовлетворяет требованию. Это просто, потому что на последних этапах вертикальной фазы и горизонтальной фазы мы имеем дело с двумя различными парами вершин.

Теперь сделайте тот же трюк, что и Вор. В каждой вершине для каждого ее исходного инцидентного ребра добавьте $k$ новых вершин. Как обычно, $k$ ahouls должны быть достаточно большими. Наконец, длина подлинного гамильтонова цикла должна быть $2k|V|$

Тхин Д. Нгуен
источник