Классы графов, в которых задачи о гамильтоновом цикле и гамильтоновом пути имеют разную сложность

При поиске Информационной системы о классах графов и их включениях я обнаружил несколько классов графов, для которых задача о гамильтоновом цикле NP-полна, а сложность задач о гамильтоновом пути НЕ известна. Некоторые из этих классов представляют собой двудольные графы максимальной степени 3, сеточные графы максимальной степени 3 и 2-связные кубические плоские графы. Также это явление относится к круговым графам и треугольным графам сетки.

Есть ли обновление сложности гамильтоновой задачи о пути на этих классах? Есть ли объяснение этому явлению?

РЕДАКТИРОВАТЬ : я нашел в базе данных классов графов странный случай графов сплошной сетки, где проблема гамильтоновых циклов находится в то время как проблема гамильтоновых путей имеет неизвестную сложность. $P$

cc.complexity-theory graph-theory Мухаммед Аль-Туркистани
источник

Интересно, есть ли интересный класс графов, для которого HP находится в но HC является полным.

P

$P$

N P

$NP$

Мухаммед Аль-Туркистани

В общем, есть ли класс графов, для которого одна из проблем (HC и HP) является полной, а другая - в или в ? Я ищу опубликованные результаты для проблем HC и HP.

N P

$NP$

P

$P$

N P I

$NPI$

Мухаммед Аль-Туркистани

Для чего бы это ни стоило (не очень), гамильтоновы пути и гамильтоновы циклы имеют разную сложность на деревьях: цикл тривиален, но путь требует линейного сканирования, чтобы увидеть, есть ли вершина степени больше двух.

Дэвид Ричерби

Маловероятно, что HP находится в а HC является неполным для любого класса графов, поскольку существует сокращение Кука с HC до HP, которое делает не более вызовов для оракула HP. Реальный вопрос заключается в том, существует ли сокращение Карпа ( ).

P

$P$

N P

$NP$

O (| E |)

$O(|E|)$

H C <_{P}^{m} H P

$HC<_P^m HP$

Мухаммед Аль-Туркистани

Ответы:

Задача о гамильтоновом пути на сеточных графах с максимальной степенью 3 является NP-полной. Доказательство содержится в CH Papadimitriou и UV Vazirani, О двух геометрических задачах, связанных с проблемой коммивояжера, Journal of Algorithms, том 5, выпуск 2, июнь 1984, страницы 231–246 (теорема 2)

Марцио де Биаси
источник

Спасибо, Марцио. Используют ли они те же определения, что и в базе данных для сеточных графиков? (поскольку они имеют разные определения в литературе)

Мухаммед аль-Тюркистани

Сетка граф является конечным, узел-индуцированной подграф

, бесконечный граф, множество вершин состоит из всех точек плоскости с целыми координатами , и в котором соединяются две вершины тогда и только тогда , когда евклидово расстояние между ними равно 1; таким образом, сеточный граф может иметь «дыры», и теорема доказана для (ограниченных) сеточных графов, в которых вершины имеют максимальную степень 3.

G^{\infty}

$G^\infty$

Марцио Де Биаси

Спасибо Марцио, так что для этого класса HC и HP имеют одинаковую сложность.

Мухаммед Аль-Туркистани

@ MohammadAl-Turkistany: еще одно примечание: сеточные графы (и сеточные графы с максимальной степенью 3) также являются двудольными, поэтому HP также должна быть NP-полной для двудольных графов с максимальной степенью 3.

Марцио Де Биаси

Произошло обновление информационной системы о графовых классах и их включениях. Теперь задача о гамильтоновом цикле и задача о гамильтоновом пути являются NP-полными на 2-связных кубических плоских графах.

Однако вычислительные сложности задач HC и HP перечислены неизвестными для одной задачи и NP-завершены для другой на круговых графах , треугольных сеточных графах и сплошных сеточных графах .

Мухаммед Аль-Туркистани
источник

Вы говорите: «... проблемы с HC и HP все еще разные ...»; возможно, лучше сказать, что «для этих классов графов HC - это NPC, но у HP все еще неизвестная сложность»

Марцио Де Биаси

@MarzioDeBiasi Спасибо за ваш ценный комментарий. Я отредактировал, чтобы отразить ваше предложение.

Мохаммад Аль-Туркистани

Я что-то пропустил? HC полиномиальное время разрешимо в графах сплошной сетки. ieeexplore.ieee.org/document/646138

Саид