Является ли проблема самой длинной трассы легче, чем проблема самой длинной трассы?

Самая длинная проблема на пути - NP-сложная. (Типичное?) Доказательство опирается на редукцию задачи о гамильтоновом пути (которая является NP-полной). Обратите внимание, что здесь путь считается простым (node-). То есть ни одна вершина не может встречаться более одного раза в пути. Очевидно, что это также является простым ребром (никакое ребро не будет встречаться более одного раза в пути).

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

Обратите внимание, что я знаю об аргументе, приведенном здесь: /programming/8368547/how-to-find-the-longest-heaviest-trail-in-an-undirected-weighted-graph Однако аргумент кажется некорректным в его текущей форме, так как он в основном показывает, что вы могли бы решить дело с простым ребром, решив дело с простым узлом на другом графе (таким образом, сокращение - неправильный путь). Не ясно, что сокращение может быть легко изменено, чтобы работать и другим способом. (Тем не менее, это показывает, что, по крайней мере, проблема с самыми длинными трассами не сложнее, чем проблема с самыми длинными трассами.)

Так есть ли какие-либо известные результаты для нахождения самых длинных трасс (простых по краю трасс)? Сложность (класс)? (Эффективный) алгоритм?

graph-theory graph-algorithms hamiltonian-paths Джаспер
источник

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

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

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

@Bangye: хорошо, но в кубических графах, если узел пересекается один раз, то должны использоваться 2 ребра ... и узел не может быть пройден снова (потому что существует только одно не пересеченное ребро). Таким образом, в кубических графах узлы не могут быть «повторены» (за исключением последнего края следа, который может быть связан с уже пройденным узлом)

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

Вот ссылка: А. А. Бертосси, Задача о краевом гамильтоновом пути NP-полна, Information Processing Letters, 13 (1981) 157-159.

Ламин

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

Йота Отачи

Из приведенных выше комментариев: задача о гамильтоновом цикле остается NP-полной даже в графах сетки с максимальной степенью 3 [1], но в этих графах для каждого обхода узла требуется два ребра, и самое большее одно ребро остается неиспользованным, поэтому узел не может быть дважды пройденный эйлеровым путем.

$G = (V,E)$ $|V|$

$u$ $V' = V \cup \{u',u''\}$ $E = E \cup \{(u,u'), (u,u'')\}$ $|V'| = |V|+2$ $u',u''$

[1] Christos H Papadimitriou, Umesh V Vazirani, О двух геометрических задачах, связанных с проблемой коммивояжера, Journal of Algorithms, том 5, выпуск 2, июнь 1984, страницы 231-246, ISSN 0196-6774

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

| E |

$|E|$

| V |

$|V|$

| E |

$|E|$

O (1)

$O(1)$

| V |

$|V|$

u^{'}, u^{″}

$u',u''$

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

Является ли проблема самой длинной трассы легче, чем проблема самой длинной трассы?

Ответы: