# depth first search – Find palindrome in directed Graph where edges are either blue or red

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.

Posted on Categories Articles