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

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?

• This is essentially the same problem as an Atcoder problem, in case you want to submit a program. May 25, 2021 at 17:51

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.