Нахождение хотя бы двух путей одинаковой длины в ориентированном графе

Предположим , что мы имеем ориентированный граф и два узла A и B . Я хотел бы знать, есть ли уже алгоритмы для расчета следующей задачи решения:$G=(V,E)$$A$$B$

Есть ли хотя бы два пути между и В одинаковой длины?$A$$B$

Как насчет сложности? Могу ли я решить это за полиномиальное время?

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

Рассмотрим граф , мы хотим знать, существуют ли два разных пути от A до B одинаковой длины. Что делать? Просто: закодируйте два пути в одном. Определим граф G ' с вершинами V × V × { 0 , 1 } . Вы делаете шаг в G ' , сделав два самостоятельных шагов в G . Дополнительный бит сообщает вам, не разделены ли два пути друг от друга.$G$$A$$B$$G'$$V \times V \times \{0,1\}$$G'$$G$

Формально существует ребро в G ′ тогда и только тогда, когда i → i ′ , j → j ′ в G и e ′ = e ∨ ( i , i ′ ) ≠ ( j , j ′ ) .$(i,j,e) \to (i',j',e')$$G'$$i \to i'$$j \to j'$$G$$e'=e ∨ (i,i')≠(j,j')$

Алгоритм проверяет, существует ли путь к ( B , B , 1 ) в G ' , который является O ( V 4 ) , или что-то вроде O ( ( V + E ) 2 ) .$(A,A,0)$$(B,B,1)$$G'$$O(V^4)$$O((V+E)^2)$

Если вы согласны с тем, что этот алгоритм корректен, то, как следствие, длина пути в не превышает 2 n 2 , поэтому потенциальные «коллизии пути» должны иметь место не позднее этой длины. Из этого наблюдения можно получить алгоритм O ( V ω log V ) , где ω - сложность умножения матриц (спросите, нужен ли вам спойлер ...).$G'$$2n^2$$O(V^{\omega} \log V)$$\omega$

Я твердо чувствую, что есть алгоритм , который использует больше структуры проблемы.$O(V+E)$

Возможно, у меня есть ответ на эту проблему, но я не уверен, что это работает.

Не важно «найти» два пути, единственная важная вещь - «знать», существуют они или нет. Я не думаю, что это полная проблема NP.

Итак, возьмите матрицу смежности . Мы можем легко предположить, что он заполнен значением 0,1. (0 = нет ребра; 1 = есть ребро) Давайте используем следующую алгебру с 3 значениями (0,1,2), где все работает как обычно, кроме: 2 + <что-то> = 2 ; 2 ∗ <все, что больше 0> = $\textbf A$$2+\text{<something>} = 2$$2*\text{<whatever greater than 0>} = 2$

Таким образом, если есть два пути одинаковой длины от я ожидаю, что существует значение p такое, что ( A p ) i , j = 2 .$i,j$$p$$(\textbf A^p)_{i,j} = 2$

Пусть - номер вершины в графе (или, скажем, A имеет размерность n × n ). Я не знаю значения p , но если я итерирую A , умножая на себя не более n 2, я должен найти ответ. (итак, p < n 2 ) (смысл в том, что я проверяю A , затем я проверяю A 2 , затем я проверяю A 3 и так далее ...)$n$$\textbf A$$n\times n$$p$$\textbf A$$n^2$$p<n^2$$\text A$$\text A^2$$\text A^3$

вот моя аргументация:

• если два пути - простые пути, хорошо, это работает; если есть, самое большее, я должен повторить раз.$n$
• $n^2$$n^2$
• $\alpha + \beta m = \gamma + \delta k$$m$$k$$\text A^q$$i$$j$$q$$\textbf A^q$$1$$i$$j$$n^2$$\delta$$\beta$$LCM(a,b)$$(a*b)/GCD(a,b)$$n$

$(\textbf A^p)_{i,j} = 2$

Я ошибаюсь?