21
$\begingroup$

Suppose we have a directed graph $G=(V,E)$ and two nodes $A$ and $B$. I would like to know if there are already algorithms for calculating the following decision problem:

Are there at least two paths between $A$ and $B$ of the same length?

How about the complexity? Can I solve it in polynomial time?

I would like to add a new constrain on the graph, maybe the problem is more solvable. On adjacency matrix, every column is not empty. So, every node has at least one arrow on input and there is also at least one node connected to itself. So if the node is the $i$-th node, then $(i,i)$ is an edge in the graph.

Improve this question
$\endgroup$
4
  • $\begingroup$ Did you mean simple paths? (visiting each node at most one time), Also are they allowed to have a common internal node? $\endgroup$
    – user742
    Jun 26, 2012 at 12:39
  • 1
    $\begingroup$ no, there are no restriction on paths. you may loop, if you want. $\endgroup$
    – Paolo Parisen T.
    Jun 26, 2012 at 12:58
  • $\begingroup$ Easy observation is this: if there is just one simple path between $A,B$, and this simple path is connected to at most one loop, you could simply say $No$, If there is at least two loops of different length connected to this simple path, you could say yes, .... (I think similar things are useful and you could prove it), But in the case of disjoint simple paths (if during prove of this you encountered to disjoint simple paths), it's NPC. $\endgroup$
    – user742
    Jun 26, 2012 at 13:08
  • 1
    $\begingroup$ @mrm: I don't see this as a duplicate. Asking for all walks is a massively time consuming operation (in general, there are an infinite number of walks), whereas the OP is asking for two (simple) paths, not all walks. $\endgroup$
    – Dave Clarke
    Jun 26, 2012 at 13:47

2 Answers 2

Reset to default
10
$\begingroup$

Consider a graph $G$, we want to know if there are two different paths from $A$ to $B$ of the same length. What to do? Simple: code two paths in one. Define graph $G'$ with vertices $V \times V \times \{0,1\}$. You make a step in $G'$ by making two independent steps in $G$. The additional bit tells you whether the two paths have already split from each other.

Formally, there is an edge $(i,j,e) \to (i',j',e')$ in $G'$ iff $i \to i'$, $j \to j'$ in $G$ and $e'=e ∨ (i,i')≠(j,j')$.

The algorithm checks if there is a path $(A,A,0)$ to $(B,B,1)$ in $G'$, which is $O(V^4)$, or something like $O((V+E)^2)$.

If you agree this algorithm is correct then, as a consequence, the path in $G'$ is of length at most $2n^2$, therefore potential "path collisions" must occur latest at that length. You can get a $O(V^{\omega} \log V)$ algorithm from this observation, where $\omega$ is matrix multiplication complexity (ask if you need a spoiler...).

I strongly feel there is a $O(V+E)$ algorithm, which uses more of the structure of the problem.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ That's elegant. $\endgroup$
    – Raphael ♦
    Jul 1, 2012 at 9:40
4
$\begingroup$

Probably i've an answer for this problem, but i'm not sill sure that it works.

It is not important to "find" the two path, the only important thing is to "know" if they exist or not. I don't think that this is an NP complete problem.

So, take the adjacency matrix $\textbf A$. We can easily suppose that it is filled with 0,1 value. (0 = no edge; 1 = there is an edge) Let's use the following algebra with 3 values (0,1,2), where everything works as usual except: $2+\text{<something>} = 2$; $2*\text{<whatever greater than 0>} = 2$

So, if there are two paths of same length from $i,j$ i'm expecting that there is a value $p$ such that $(\textbf A^p)_{i,j} = 2$.

Let $n$ is the number of vertex in the graph (or, let's say, that $\textbf A$ has dimension $n\times n$). I don't know the value of $p$, but if i iterate $\textbf A$ by multiplying with itself for at most $n^2$ i should find the answer. (so, $p<n^2$) (the sense is that i check $\text A$, then i check $\text A^2$, then i check $\text A^3$ and so on...)

here is my argumentation:

  • if the two paths are simple paths, well, it works; if there are, at most i have to iterate $n$ times.
  • If there is at least one neasted cycle or there is a path with two cycles, well, i have to find the least common multiple (LCM). $n^2$ is a bigger value for sure and in less than $n^2$ times if there is i should have to find them.
  • If the two paths are two distinct paths, both with one cycle, then it's more or less similar to finding a solution for this two equation: $\alpha + \beta m = \gamma + \delta k$, where $m$ and $k$ are the length of these two distinct cycles. Matrix multiplication $\text A^q$, as defined above, says "is there a path from $i$ to $j$ whose length is $q$?" So, if $\textbf A^q$ is grater than $1$ it means that there are more paths leading from $i$ to $j$. By iterating the matrix $n^2$ times we pass through all the possible combination of $\delta$ and $\beta$. Indeed, $LCM(a,b)$ is defined as $(a*b)/GCD(a,b)$ and no cycle can be greater than $n$.

I stop to iterate once i found $(\textbf A^p)_{i,j} = 2$.

am i wrong?

Improve this answer
$\endgroup$
3
  • $\begingroup$ I tried the same and I encountered some problems/uncertainties: 1) What if the paths are connected to more than one cycle? Do you have to "check" all combinations (in the worst case, every node lies on exponentially many cycles!), blowing up the upper bound, or is it sufficient to consider only one for each? 2) Because of the constant offsets $\alpha$ and $\gamma$, is the LCM really an upper bound? $\endgroup$
    – Raphael ♦
    Jun 29, 2012 at 13:01
  • $\begingroup$ By the way, there is no need for a funky algebra: just stop the moment you compute a $2$ as matrix entry. $\endgroup$
    – Raphael ♦
    Jun 29, 2012 at 13:02
  • $\begingroup$ @Raphae 1) if there is a path with two cycles, then there are for sure two path of same lenght. one that loops on first cycle and one that loops on second. how much do they have to loop? exactely the LCM of the lenght of both cycles. this is bounded by $n^2$, where $n$ is the number of vertexes in the graph. 2) LCM is the upper bound (in the case 1)) because LCM(a,b) is bounded by a*b plus $\alpha$ and $\gamma$ offsets; so, in total we have $LCM(a,b) + \alpha+\gamma < a*b+\alpha + \gamma$. we know that $\alpha+\gamma+a+b < n$, so $a*b+\alpha+\gamma$ is less than $n^2$. $\endgroup$
    – Paolo Parisen T.
    Jun 29, 2012 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.