Перечисление всех минимальных направленных циклов ориентированного графа

Question

У меня есть ориентированный граф, и моя задача состоит в том, чтобы перечислить все минимальные (циклы, которые нельзя построить как объединение других циклов) направленных циклов этого графа. Это отличается от того, что выводит алгоритм Тарьяна. Например, для ориентированного графа на этой странице википедии я хотел бы получить c <-> d и d <-> h как два отдельных направленных цикла.

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

Кто-нибудь знает ответ на эту проблему?

Заранее спасибо !!!

Answer 1

Если мы ищем кратчайший цикл, он кажется достаточно простым.

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

• Продолжайте, пока больше не будет узла.

• Когда вы обработали все узлы (вершины), у вас есть минимальные циклы, которые вы ищете ... но есть хитрость.

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

При таком наивном подходе сложность была бы O (V. (E + V)), где V - количество вершин, а E - количество ребер. O (E + V) начинается с ширины, и в худшем случае вам нужно выполнить BFS V раз. Следовательно, это определенно полином лучше. Я полагаю, что то, что я описал, действительно O (log (V). (E + V)) в среднем случае, но я еще не доказал (если это правда).

Answer 2

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

Рассмотрим n/2 наборов размера 2 и расположим их циклически: A_1, ..., A_{n/2} и используйте соглашение A_{n/2+1}=A_1. Поместите ребро между двумя вершинами тогда и только тогда, когда они лежат в наборах последовательных индексов (поэтому элементы в A_{n/2} также связаны с элементами в A_1 в соответствии с вышеуказанным соглашением). Если вас интересуют орграфы, а не простые графы, направьте ребра так, чтобы они всегда указывали на вершину, лежащую в наборе с большим индексом, или, в случае A_{n/2} и A_1, указывайте на вершины в A_{n/2} к тем, кто в A_1.

Очевидно, что в этом графе длины n/2 есть 2^{n/2} минимальные циклы, потому что все подмножества размера n/2, содержащие ровно одну вершину в каждом A_i, являются таким циклом. Если вы хотите перечислить их все с помощью алгоритма, этот алгоритм должен сделать как минимум 2^{n/2} шагов.

Answer 3

Может быть, перечисление НЕЗАВИСИМЫХ циклов поможет?

Я бы попробовал следующее.

1. Сначала, чтобы узнать, какие вершины участвуют в циклах, сделайте транзитивное замыкание. Это алгоритм O (V ^ 3).
2. Удалить все остальные вершины.
3. Теперь существует полное независимое покрытие циклов оставшегося графа (это слабое место моей идеи, я не могу доказать, что циклы будут независимыми)
4. Решение для этого - алгоритм "максимальное совпадение пар в двудольном графе".

4,1. Превратите каждую вершину v в вашем графе (G) в 2 (v1 и v2), поместите каждую в разные части двудольного графа (G2).

4,2. Для каждого ребра e (v, u) в G добавьте ребро из 1-й части G2 во 2-е - e (v1, u2).

4,3. Найти максимальное совпадение пары в G2. Это подмножество ребер G2.

5 Это подмножество соответствует максимальному (полному) набору независимых циклов в G.

Answer 4

Мы ищем все простые циклы, а не только самые короткие или самые дешевые. (Если просто правильный термин - я имею в виду циклы, которые не пересекаются.)

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

Я не уверен в сложности этого, но похоже, что O (EV ^ 2).

EDIT:
Теперь, когда я думаю об этом, вы, вероятно, можете добраться до O (EV), начав с одного продавца на узле с наименьшим номером. Когда все его потомки мертвы, начните снова с продавца на узле с наименьшим номером, который еще не посещался. Повторяйте, пока все узлы не будут посещены.