Задача о гамильтоновом пути

Задача о гамильтоновом пути и задача о гамильтоновом цикле — это задачи определения, существует ли гамильтонов путь или гамильтонов цикл в заданном графе (ориентированном или неориентированном). Обе задачи NP-полны[1].

Связь задач о гамильтоновом пути и гамильтоновом цикле

Существует простое отношение между задачами нахождения гамильтонова пути и нахождения гамильтонова цикла. В одном направлении задача о гамильтоновом пути для графа эквивалентна задаче о гамильтоновом цикле в графе H, полученного из графа G путём добавления новой вершины и соединения её со всеми вершинами графа G. Таким образом, поиск гамильтонова пути не может быть существенно медленнее (в худшем случае, как функция числа вершин), чем поиск гамильтонова цикла.

В обратном направлении задача о гамильтоновом цикле для графа G эквивалентна задаче о гамильтоновом пути в графе H, полученном копированием одной вершины v графа G (в v'), то есть вершина v' будет иметь ту же окрестность, что и v, и добавлением двух вспомогательных вершин степени один, одна из которых соединена с v, а другая с v'[2].

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

Алгоритмы

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

Ранний точный алгоритм нахождения гамильтонова цикла в ориентированном графе был алгоритмом перебора (алгоритм Мартелло)[3].

Процедура поиска Франка Рубина[4] разбивает рёбра графа на три класса — те, которые должны быть на пути, те, которые пути принадлежать не могут, и рёбра, для которых решение не принято. В процессе поиска набор правил принятия решений классифицирует рёбра, для которых решение не принято, и определяет, остановиться или продолжить поиск. Алгоритм разбивает граф на компоненты, которые могут быть обработаны отдельно.

Для решения задачи за время может быть использован алгоритм динамического программирования Беллмана, Хелда и Карпа. В этом методе определяется для каждого набора S вершин и каждой вершины v из S, существует ли путь, проходящий через все вершины S и заканчивающийся в v. Для каждой пары (S,v) путь существует тогда и только тогда, когда v имеет соседнюю вершину w такую, что существует путь для , который можно получить из уже полученной информации динамического программирования[5][6].

Андреас Бьёрклунд даёт альтернативный подход, использующий принцип включения/исключения для сокращения числа перебираемых гамильтоновых циклов и задача подсчёта циклов может быть решена путём вычисления определителя некоторой матрицы.

Используя этот метод, он показал, как решить задачу о гамильтоновом цикле для произвольных графов с n вершинами с помощью алгоритма Монте-Карло за время . Для двудольных графов этот алгоритм можно улучшить до времени [7].

Для графов с максимальной степенью три аккуратный поиск с возвратом может найти гамильтонов цикл (если таковой существует) за время [8].

Гамильтоновы пути и циклы можно найти с помощью SAT решателя.

Ввиду сложности решения задач о гамильтоновом пути и цикле на обычных компьютерах, они изучались для нестандартных моделей вычислений. Например, Леонард Адлеман показал, что задачи о гамильтоновом пути могут быть решены с помощью ДНК-компьютера. Используя параллелелизм, свойственный химическим реакциям, задача может быть решена с помощью нескольких шагов химических реакций, линейно зависящих от числа вершин графа. Однако это требует факториальное число молекул ДНК, участвующих в реакции[9].

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

Сложность

Задача нахождения гамильтонова цикла или пути имеет сложность FNP[англ.]. Аналогичная задача разрешимости — проверить, существует ли гамильтонов цикл или путь. Ориентированные и неориентированные задачи о гамильтоновом цикле являлись двумя из 21 NP-полных задач Карпа. Они остаются NP-полными даже для неориентированных планарных графов максимальной степени три[11], для ориентированных планарных графов с полустепенью входа и выхода, не превосходящими двух[12], для неориентированных планарных 3-регулярных двудольных графов без мостов, для 3-связных 3-регулярных двудольных графов[13], подграфов квадратной решётки[14] и для кубических подграфов квадратной решётки[15].

Однако 4-связные планарные графы всегда гамильтоновы, согласно результату Татта, а задача нахождения гамильтонова цикла в этих графах может быть выполнена за линейное время[16] путём вычисления так называемого пути Татта. Татт доказал этот результат, показав, что любой 2-связный планарный граф содержит путь Татта. Пути Татта, в свою очередь, можно вычислить за квадратичное время даже для 2-связных планарных графов[17], что может быть использовано для поиска гамильтоновых циклов и длинных циклов в обобщённых планарных графах.

Складывая всё вместе, остаётся открытой задача, всегда ли 3-связные 3-регулярные двудольные планарные графы должны содержать гамильтонов цикл и если должны, задача, ограниченная этими графами, не будет NP-полной (см. статью «Гипотеза Барнетта»).

В графах в которых все вершины имеют нечётную степень, довод, связанный с леммой о рукопожатиях, показывает, что число гамильтоновых циклов через фиксированное ребро всегда чётно, так что если дан один гамильтонов цикл, то и другой должен существовать[18]. Однако поиск этого второго цикла не выглядит как простая вычислительная задача. Пападимитриу определил класс сложности PPA[англ.], чтобы собрать вместе задачи, подобные этой[19].

Примечания

  1. ↑ Garey, Johnson, 1979, с. 199—200, A1.3: GT37 - 39.
  2. ↑ graph theory - Reduction from Hamiltonian cycle to Hamiltonian path - Mathematics Stack Exchange. Дата обращения: 18 февраля 2019. Архивировано 23 апреля 2019 года.
  3. ↑ Martello, 1983, с. 131–138.
  4. ↑ Rubin, 1974, с. 576–80.
  5. ↑ Bellman, 1962, с. 61–63.
  6. ↑ Held, Karp, 1962, с. 196–210.
  7. ↑ Björklund, 2010, с. 173–182.
  8. ↑ Iwama, Nakashima, 2007, с. 108–117.
  9. ↑ Adleman, 1994, с. 1021–1024.
  10. ↑ Oltean, 2006, с. 217–227.
  11. ↑ Garey, Johnson, Stockmeyer, 1974, с. 47–63.
  12. ↑ Plesńik, 1979, с. 199–201.
  13. ↑ Akiyama, Nishizeki, Saito, 1980–1981, с. 73–76.
  14. ↑ Itai, Papadimitriou, Szwarcfiter, 1982, с. 676–686.
  15. ↑ Buro, 2000, с. 250–261.
  16. ↑ Chiba, Nishizeki, 1989, с. 187–211.
  17. ↑ Schmid, Schmidt, 2018.
  18. ↑ Thomason, 1978, с. 259–268.
  19. ↑ Papadimitriou, 1994, с. 498–532.

Литература

  • Michael R. Garey, David S. Johnson. [Computers and Intractability: A Guide to the Theory of NP-Completeness Computers and Intractability: A Guide to the Theory of NP-Completeness]. — W.H. Freeman, 1979. — ISBN 978-0-7167-1045-5.
  • Silvano Martello. An Enumerative Algorithm for Finding Hamiltonian Circuits in a Directed Graph // ACM Transactions on Mathematical Software. — 1983. — Т. 9, вып. 1. — С. 131–138. — doi:10.1145/356022.356030.
  • Frank Rubin. A Search Procedure for Hamilton Paths and Circuits // Journal of the ACM. — 1974. — Т. 21, вып. 4. — С. 576–80. — doi:10.1145/321850.321854.
  • Richard Bellman. Dynamic programming treatment of the travelling salesman problem // Journal of the ACM. — 1962. — Т. 9. — С. 61–63. — doi:10.1145/321105.321111.
  • Held, Karp. A dynamic programming approach to sequencing problems // J. SIAM. — 1962. — Т. 10, вып. 1. — С. 196–210. — doi:10.1137/0110015.
  • Andreas Björklund. Determinant sums for undirected Hamiltonicity // Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS '10). — 2010. — С. 173–182. — ISBN 978-1-4244-8525-3. — doi:10.1109/FOCS.2010.24.
  • Kazuo Iwama, Takuya Nakashima. An improved exact algorithm for cubic graph TSP // Proc. 13th Annual International Conference on Computing and Combinatorics (COCOON 2007). — 2007. — Т. 4598. — С. 108–117. — (Lecture Notes in Computer Science). — ISBN 978-3-540-73544-1. — doi:10.1007/978-3-540-73545-8_13.
  • Leonard Adleman. Molecular computation of solutions to combinatorial problems // Science. — 1994. — Ноябрь (т. 266, вып. 5187). — С. 1021–1024. — doi:10.1126/science.7973651. — Bibcode: 1994Sci...266.1021A. — PMID 7973651. — JSTOR 2885489.
  • Mihai Oltean. A light-based device for solving the Hamiltonian path problem // Unconventional Computing. — Springer LNCS 4135, 2006. — doi:10.1007/11839132_18.
  • Michael Garey, David S. Johnson, Larry Stockmeyer. Some simplified NP-complete problems // Proc. 6th ACM Symposium on Theory of Computing (STOC '74). — 1974. — С. 47–63. — doi:10.1145/800119.803884.
  • Plesńik J. The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two // Information Processing Letters. — 1979. — Т. 8, вып. 4. — С. 199–201. — doi:10.1016/0020-0190(79)90023-1.
  • Takanori Akiyama, Takao Nishizeki, Nobuji Saito. NP-completeness of the Hamiltonian cycle problem for bipartite graphs // Journal of Information Processing. — 1980–1981. — Т. 3, вып. 2. — С. 73–76.
  • Alon Itai, Christos Papadimitriou, Jayme Szwarcfiter. Hamilton Paths in Grid Graphs // SIAM Journal on Computing. — 1982. — Т. 4, вып. 11. — С. 676–686. — doi:10.1137/0211056.
  • Michael Buro. Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs // Conference on Computers and Games. — 2000. — Т. 2063. — С. 250–261. — (Lecture Notes in Computer Science). — ISBN 978-3-540-43080-3. — doi:10.1007/3-540-45579-5_17.
  • Norishige Chiba, Takao Nishizeki. The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs // Journal of Algorithms. — 1989. — Т. 10, вып. 2. — С. 187–211. — doi:10.1016/0196-6774(89)90012-6.
  • Andreas Schmid, Jens M. Schmidt. Computing Tutte Paths // Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP'18), to appear.. — 2018.
  • Thomason A. G. Hamiltonian cycles and uniquely edge colourable graphs // Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977). — 1978. — Т. 3. — С. 259–268. — (Annals of Discrete Mathematics). — ISBN 9780720408430. — doi:10.1016/S0167-5060(08)70511-9.
  • Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence // Journal of Computer and System Sciences. — 1994. — Т. 48, вып. 3. — С. 498–532. — doi:10.1016/S0022-0000(05)80063-7.