Обнаружение циклов нечетного общего веса в графе с {0,1}-взвешенными ребрами

Question

Учитывая взвешенный по ребрам орграф $G = (V, E \subseteq V^2, w \in E o \{0, 1\})$, существует ли алгоритм, который возвращает TRUE если в этом графе существует цикл, общий вес которого нечетен и FALSE в противном случае, который работает быстрее, чем $O((|V| + |E|)(c + 1))$ (где $c$ — количество простых циклов в графе, что, конечно, $\Omega(2^{|V|})$)?

Как следует из вопроса, я уже придумал алгоритм, который работает в $O((|V| + |E|)(c + 1))$ время.Этот алгоритм предполагает первый запуск Простой алгоритм перечисления циклов Джонсона, что дает нам все простые циклы на графике.С even + even = even, а все циклы состоят из сложения простых циклов, граф содержит цикл нечетной длины тогда и только тогда, когда он содержит простой цикл нечетной длины.Таким образом, мы просто вычисляем четность простых циклов и возвращаем TRUE если среди них есть нечетные, и FALSE в противном случае.

Может ли кто-нибудь придумать более эффективный подход?В идеале это не просто «замена алгоритма Джонсона другим простым алгоритмом перечисления циклов, который имеет немного лучшую асимптотику», поскольку графики, с которыми я имею дело, на самом деле не такие большие, и в результате вполне могут доминировать постоянные факторы.

Answer 1

Вы можете решить это в $O(|V| \cdot |E|)$ время.

Постройте орграф с вершинами вида $\langle v,b angle$ где $v \in V$, $b \in \{0,1\}$, следующее:для каждого края $v \stackrel{t}{ o} w$ в свой график добавьте ребра $\langle v,b angle o \langle w,b + t \bmod 2 angle$ для каждого $b \in \{0,1\}$ к новому графику.

Тогда для каждого $v \in V$, проверьте, есть ли путь от $\langle v,0 angle$ к $\langle v,1 angle$ или из $\langle v, 1 angle$ к $\langle v,0 angle$ на этом новом графике.Это можно сделать с помощью двух поисков DFS на каждую вершину. $v \in V$;каждый поиск DFS занимает $O(|E|)$ время, поэтому общее время работы равно $O(|V| \cdot |E|)$ время.Поиск можно ускорить, если один раз разложить новый граф на сильно связанные компоненты, а затем выполнить поиск в наборе компонентов (метаграфе).

Answer 2

Постройте матрицу инцидентности ребра-вершины:строки соответствуют ребрам, столбцы — вершинам, и существует $1$ если ребро инцидентно вершине.Добавьте еще один столбец, полный $1$х.Вы хотите знать, существует ли подмножество строк, суммирующихся с вектором. $0,\ldots,0,1$ (по модулю 2).Вы можете это узнать, используя метод исключения Гаусса за полиномиальное время.

Что здесь происходит?Давайте рассмотрим исходную матрицу инцидентности ребер-вершин.Сумма строк, соответствующих циклам, равна нулю, поскольку каждая вершина встречается ровно в двух ребрах.И наоборот, если у нас есть набор строк, сумма которых равна нулю, то степень каждой вершины четная.Начиная с произвольного края, мы можем проследить путь, который в конечном итоге закроется сам на себя.Удалим соответствующий цикл (который не обязательно должен содержать исходное ребро) и продолжим.Таким образом, мы видим, что набор строк, сумма которых равна нулю, соответствует непересекающемуся по ребру объединению циклов.

Добавив дополнительный $1$ столбца в матрицу, мы отслеживаем четность цикла.Нечетные циклы суммируются с вектором $0,\ldots,0,1$.И наоборот, если сумма строк равна $0,\ldots,0,1$, то он соответствует набору циклов, общая длина которых нечетна, поэтому один из циклов нечетен.

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