3
$\begingroup$

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?

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

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
0

Your Answer

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