Особые случаи Graphic TSP

9

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

Какова сложность Graphic TSP на ограниченных трехуровневых графах?

Существуют ли какие-либо особые случаи графического TSP с нетривиальными алгоритмами за полиномиальное время?

Шива Кинтали
источник

Ответы:

10

Насколько я знаю, динамическое программирование делает свое дело

Статья Клейна о TSP для плоских графов содержит подробности для плоских графов с ограниченной шириной дерева. Если график не плоский, динамическая программа работает медленнее (зависимость от ширины дерева хуже).

Филип Н. Клейн: Линейная схема аппроксимации времени для TSP в неориентированных плоских графах с краевыми весами . SIAM J. Comput. 37 (6): 1926-1952 (2008) ( PDF на сайте Филипа Кляйна )

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

Эрик Д. Демейн, Мохаммад Таги Хаджиагайи, Боян Мохар: Аппроксимационные алгоритмы посредством разложения сжатия . Combinatorica 30 (5): 533-552 (2010) ( статья на веб-сайте Эрика Демейна )

Эрик Д. Демейн, Мохаммад Таги Хаджиагайи, Кен-ичи Каварабаяси: Разложение со сжатием в графах без минорных мин и алгоритмических приложениях . STOC 2011: 441-450

Видеоролики об этих конструкциях PTAS см. В разделе « Планарная TSP» и « Незначительная TSP» (опять же, не фокусируясь на части ширины дерева).

Кристиан Соммер
источник
4

Я верю вК графы, задача точно решаема во времени полинома в N а также КК, Это справедливо и для метрической задачи на весовых ограниченных графах ширины. Один выполняет динамическую программу, где для каждой сумки у вас есть вход для каждого возможного пути пересечения с одной стороны сумки на другую. СК узлы в сумке, один имеет максимум ККвозможные конфигурации перехода от одной стороны сумки к другой. Фактически это работает для любого семейства графов, которое можно разбить с помощью небольших разделителей вершин на компоненты, принадлежащие к семейству (и, таким образом, в частности, имея сами небольшие разделители вершин). Время работы будетпоLY(N,КК) если разделители имеют размер К,

Кунал
источник
4

Взгляните на Марека Сигана, Джеспера Недерлофа, Марцина Пилипчука, Михаила Пилипчука, Йохана ван Ройя, Якуба Онуфрия Войтащика, « Решение проблем со связностью, параметризованных шириной дерева, за один экспоненциальный промежуток времени », 2011.

Я думаю, что вы можете использовать их идеи, чтобы получить рандомизированный поли(N)2О(К) алгоритм времени для treewidth-К графики на N Вершины.

Андреас Бьёрклунд
источник