«Направленные» проблемы, которые легче, чем их «ненаправленные» варианты.

Я читал лекцию по сортировке блинов и сказал, что:

• Сортировка по обращению является NP-трудной
• «подписан» сортировка по разворотов в P .

Что заставило меня задуматься. В некотором смысле «подписанная» сортировка является «направленной» - вы можете рассматривать знак как направление (и действительно, это мотивация эволюционной биологии). Но это более простая проблема! Это необычно, потому что обычно (по крайней мере, на графиках) направленные проблемы сложнее (или, по крайней мере, так же сложно), как и их ненаправленные аналоги.

Принимая щедрое определение «направленного», есть ли примеры направленных проблем, которые легче, чем их неориентированные аналоги?

Подсчет эйлеровых схем для ориентированных графов выполним за полиномиальное время с использованием теоремы BEST , в то время как, по-видимому, та же проблема для неориентированных графов является # P-полной .

Интересный и не очень известный случай заключается в следующем. Предположим, у нас есть гранично-взвешенный граф и корневой узел . Мы хотим, чтобы подграф минимальной стоимости таким, чтобы было непересекающихся с ребром путей от до каждого узла графа. Когда это проблема минимальной себестоимости в ориентированных графах и в неориентированных графах, она эквивалентна проблеме MST. Оба разрешимы в многократном времени, хотя ненаправленный случай легче. Однако эта проблема разрешима по времени в ориентированных графах для любого то время как в неориентированных графах она NP-Hard для (так как она захватывает минимальную стоимость$G$$r$$G$$k$$r$$k=1$$k$$k=2$$2$-подключенная задача подграфа).

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

Вот проблема, которая, как я недавно понял, на неориентированных графах выглядит сложнее, чем на ориентированных.

Предположим, у вас есть график с положительным и отрицательным весом ребер, и вас просят обнаружить отрицательный весовой цикл. Существует алгоритм масштабирования для этой задачи для ориентированных графов Гольдберга'93 (А.В. Гольдберг. 1993. Алгоритмы масштабирования для задачи кратчайших путей. В SODA '93.), Выполняемые за время O ( ) где - количество ребер, - число вершин, а - наибольшее абсолютное значение веса ребра. Напротив, та же проблема в неориентированных графах имеет гораздо худшие алгоритмы. Насколько мне известно, наиболее известным является Габов'83 (HN Gabow. 1983. Эффективный метод сокращения для проблемных подграфов и двунаправленных проблем сетевого потока. В STOC '83.) И работает в O (min (mnCn3,mnlog$m\sqrt{n}\log C$$m$$n$$C$$n^3, mn\log n$)) время. Есть также подход, использующий T-соединения, который дает то же самое время выполнения, я не помню, где я видел это как бы то ни было.

Проблема отрицательного цикла является критической при разработке алгоритмов SSSP с одним источником, и неудивительно, что лучшие времена выполнения SSSP в ориентированных и ненаправленных графах с произвольными весами имеют одинаковое время выполнения - O ( ) и O (min ( )) соответственно.n3,mnlog$m\sqrt{n}\log C$$n^3, mn\log n$