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?

  • $\begingroup$ This is essentially the same problem as an Atcoder problem, in case you want to submit a program. $\endgroup$
    – Sawarnik
    Commented May 25, 2021 at 17:51

1 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.


Your Answer

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