Я хочу простой гаджет, чтобы доказать NP-полный планарный гамильтонов цикл (из гамильтонов цикла)

Известно, что гамильтонов цикл (для краткости Хэм) NP-полон, а планарный цикл Хэма NP-полон. Доказательство для плоского цикла Хэма не из цикла Хэма.

Есть ли хороший гаджет, который с учетом графа G заменит все пересечения некоторым плоским гаджетом, чтобы у вас был планарный граф G 'такой, что

G имеет цикл Хэма, если G 'имеет цикл Хэма.

(Я буду счастлив с вариантами, такими как путь ветчины или направленный цикл ветчины или направленный путь ветчины.)

cc.complexity-theory np-hardness planar-graphs hamiltonian-paths Билл ГАЗАРХ
источник

Несколько тривиальное наблюдение. Предположим, что вы вставляете и ребра и пересекаются, причем появляются по часовой стрелке вокруг точки пересечения. Замените его гаджетом , имеющим четыре точки входа соответствующие . Если гамильтонов цикл в использует оба ребра и то в соответствующий цикл должен сам пересекаться. Это, конечно, предполагает самую наивную интерпретацию того, что такое «гаджет», а также того, что гамильтонов цикл в

G

$G$

(x, y)

$(x,y)$

(u, v)

$(u,v)$

x, v, y, u

$x,v,y,u$

P_{x v y u}

$P_{xvyu}$

x^{'}, v^{'}, y^{'}, u^{'}

$x',v',y',u'$

x, v, y, u

$x,v,y,u$

G

$G$

(x, y)

$(x,y)$

(u, v)

$(u,v)$

G^{'}

$G'$

G^{'}

$G'$ должен следовать тем же края, что и соответствующий цикл в .

G

$G$

Марек Чробак

Что такое Хэм Цикл? Пожалуйста, не думайте, что все понимают ваши сокращения.

Tsuyoshi Ito

@MarekChrobak: Я согласен с вашим замечанием. Вы даете два способа избежать вашего аргумента. Я думаю, что наиболее естественным является второй: существует гамильтонов цикл с в если существует гамильтонов цикл с .

x \to y \to \dots \to u \to v \to \dots \to x

$x\to y\to\dotsb\to u\to v\to\dotsb\to x$

G

$G$

x \to x^{'} \to \dots \to u^{'} \to u \to \dots \to y \to y^{'} \to \dots \to v^{'} \to v \to \dots \to x

$x\to x'\to\dotsb \to u'\to u\to\dotsb\to y\to y'\to\dotsb\to v'\to v\to\dotsb\to x$

Бруно

@Tsuyoshi: это означает гамильтонов цикл. Я думаю, что разумно предположить, что каждый может понять это.

Домоторп

@ Билл: мне интересно, почему вы думаете, такой гаджет должен существовать. Число пересечений при встраивании произвольного графа в плоскость может быть очень большим ( для полного графа - см. Лемму о пересечении). Итак, если вы начнете с графа с ребрами и множеством ребер (скажем, около квадратичного), то вложенный граф с пересечениями, добавленными в виде вершин, имеет совершенно иную структуру ...

Θ (n^{4})

$\Theta(n^4)$

n

$n$

Сариэль Хар-Пелед

Ответы:

Нет. По крайней мере, нет "хорошего" гаджета для одного кроссовера.

Пусть и - крест, который мы хотим заменить. $(a, b)$ $(x,y)$ введите описание изображения здесь

Есть много случаев для нашего графа , но мы должны удовлетворить по крайней мере следующие четыре. Случай 1: есть хотя бы один гамильтонов цикл, но ни один из них не использует ни одного ребра. Случай 2: существует хотя бы один цикл, и во всех циклах используется ровно одно из двух ребер. Случай 3: есть хотя бы один цикл, и все циклы используют оба ребра. Случай 4: нет гамильтонова цикла. $G$

Если в нашем гаджете есть две (или более) вершины для каждой из смежных со всеми одинаковыми соседями (так что и сохраняют соседей ), то не обязательно будет плоской. Чтобы удовлетворить первый из наших вышеописанных случаев, у нас не может быть новых вершин в гаджете. $a, b, x, y$ $a_0$ $a_1$ $a$ $G'$

Чтобы удовлетворить описанный выше случай 3, в гаджете должно быть как минимум два ребра. Ни плоская, ни покрывающая пара, ни удовлетворяют случаю 2, поэтому нам нужно третье ребро. Без ограничения общности, пусть эти три будут . $(a, x), (y, b)$ $(a, y), (x, b)$ $(a, y), (y, b), (x,b)$

Однако эта замена нарушает четвертый случай, потому что может содержать гамильтонов цикл, когда не содержит. Возьмем, например, где и . не плоская и не имеет гамильтонова цикла. $G'$ $G$ $G = (V, E)$ $V = \{a, b, x, y, p, q, r, s, t\},$ $E = \{(a, b), (x, y), (a, r), (a, p), (a, q), (b, s), (b, x), (p, s), (p, t), (p, y), (q, x), (r, y), (t, x)\}$ $G$ введите описание изображения здесь

Тогда где . плоская и имеет гамильтонов цикл ( ). $G' = (V, E')$ $E' = \{(a, y), (y, b), (x, b)\} \cup$ $\{(x, y), (a, r), (a, p), (a, q), (b, s), (p, s), (p, t), (p, y), (q, x), (r, y), (t, x)\}$ $G'$ $a, q, x, t, p, s, b, y, r, a$

Обратите внимание, что если бы ребро не было добавлено вместо , то у не было бы гамильтонова цикла. Кажется, что вы должны знать о возможном цикле, чтобы правильно выбрать ребро. $(b, y)$ $(a, x)$ $G'$

Аналогичная проблема существует для того, чтобы гаджет включал одно из диагональных ребер, например: . $(a, b), (a, y), (x, b)$

Поскольку добавление трех ребер ломает случай 4, добавление большего количества не поможет.

Таким образом, «красивый» гаджет не существует. Может случиться так, что существует гаджет, который уделяет больше внимания соседям каждого из и , но это не кажется очень «хорошим». $a, b, x$ $y$

(Примечание: пожалуйста, дайте мне знать, если я сделал какие-либо ошибки выше!)

( ~~Примечание 2: у меня были хорошие цифры, но я не могу их опубликовать.~~ Опубликовано.)

рукав моря
источник

Я думаю, что вы должны быть в состоянии опубликовать цифры сейчас.

Юкка Суомела