1
$\begingroup$

Is there an algorithm that can efficiently solve the following question?

Given a directed acyclic graph G with n vertices each assigned a random color from a set of size <= n - 1 colors, a source vertex s, and two distinct vertices a and b both having the same color and reachable from s.

Determine if there exists at least one path from s to a and one path from s to b that have the same sequence of vertex colors.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ What are your thoughts? What progress have you made? What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$
    – D.W. ♦
    Commented Jan 19, 2020 at 19:27
  • $\begingroup$ I tried creating a graph G’ that reversed the edge directions so I could trace back from a and b to s. Using G’ I first attempted separate DFS searches from a and b storing a list of path sequences for each traversal and then comparing the results for an equal path sequence. $\endgroup$
    – azd01
    Commented Jan 19, 2020 at 20:56
  • $\begingroup$ Then I tried using a BFS of G’ from both a and b adding vertices from each level only when that vertex’s color exists at that level of both a and b’s search path. $\endgroup$
    – azd01
    Commented Jan 19, 2020 at 20:56

2 Answers 2

Reset to default
2
$\begingroup$

Hint:

Use the techniques in How hard is finding the shortest path in a graph matching a given regular language?.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the hint. I'm still at the intro to algorithms level, so it's going to take some time for me to figure out how to apply that solution, but I'll try to see if I can use this. $\endgroup$
    – azd01
    Commented Jan 20, 2020 at 2:30
  • $\begingroup$ @JohnL., naah, the running time if you use the hint properly is $O(|E|^2)$, much faster than brute force. See Optidad's answer for the expanded version. $\endgroup$
    – D.W. ♦
    Commented Jan 20, 2020 at 17:24
  • $\begingroup$ @D.W. Oh, right, I thought the question asks for two disjoint paths. $\endgroup$
    – John L.
    Commented Jan 20, 2020 at 20:14
2
$\begingroup$

Let's take the initial graph $G=(V, E)$ and create a new graph $G'=(V', E')$ where every vertex $x$ is a state representing a pair ($i$, $j$) of vertices of $G$. So basically, for $N$ vertices in $G$, there are $N^2$ vertices in $G'$

In $G'$, there is an edge from $x_1 = (i_1, j_1)$ to $x_2 = (i_2, j_2)$ iif there are both an edge from $i_1$ to $i_2$ and an edge from $j_1$ to $j_2$ in $G$. Thus, a path in $G'$ of length $k$ corresponds to two different paths in $G$ having the same length $k$.

Now, let's resolve the problem, the same color sequence has to be followed by the two paths. So in $G'$, only vertices representing a pair of identical color vertices in $G$ are allowed. By running a BFS/DFS from $(s, s)$ to $(a, b)$ in this new graph, using only the allowed vertices, one can find if there is a solution to the problem.

The time complexity is $O(|E|^2)$ at worst case (all vertices having the same color). But if there are $c$ colors having rather equivalent populations in $G$, it falls to $O(|E|^2/c)$.

Also note, that you do not have to build explicitely $G'$ to explore it !

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks. This really helped me see how to use the approach for this problem. $\endgroup$
    – azd01
    Commented Jan 20, 2020 at 22:56

Your Answer

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

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