Find palindrome in directed Graph where edges are either blue or red

Question

This is the given task: Suppose you are given an arbitrary directed graph G in which each edge is colored either red or blue, along with two special vertices s and t.

Describe an algorithm that either computes a walk from s to t such that the pattern of red and blue edges along the walk is a palindrome, or correctly reports that no such walk exists.

I already know the solution involves DFS in some way but I don't know how to check if a palindromic path doesn't exist. Since it's not necessarily an acyclic graph there are infinitely many paths that can potentially form a palindrome. So how do I go about this problem?

Answer 1

Here's a possible algorithm.

Construct a graph $G'$ with $|V|^2$ vertices where each vertex is labeled with the pair $(a, b)$ with $a, b$ being vertices in $G$. Then, construct all possible edges $(a, b) \to (c, d)$ in $G'$ where two edges $c \to a$ (note the order) and $b \to d$ exist in $G$ with the same color.

Then to find an odd-length palindrome you simply check if $(s, t)$ is reachable from any $(x, x)$ in $G'$. To find an even-length palindrome check if $(s, t)$ is reachable from any $(a, b)$ in $G'$ under the condition that $a \to b$ exists (regardless of color) in $G$.

---

The idea is to extend the palindrome from the middle out. The vertices $(l, r)$ in $G'$ represent the leftmost and rightmost symbol in our palindrome, and the way we constructed the edges in $G'$ corresponds to all valid ways to extend the palindrome.