# Traversing the edges of a labeled 2-regular graph based on a binary string

Let $$G$$ be a $$2$$-regular graph. Each edge of the graph is labeled with either 0 or 1. Given a such a graph and a staring vertex $$u$$ and $$l$$ length string of 0 and 1, we have to follow the edges of the graph $$G$$ based upon given string. We can assume that a solution always exists.

What is the best algorithm for such problem? I can solve this problem in $$O(l)$$ time. I am looking for an algorithm with better runtime answer.

• I don't quite understand your rule for choosing an edge (what if multiple edges have the correct label?), but even reading the string already takes $\mathcal{O}(l)$ time, so there is no hope of doing better. – Tassle Dec 2 '19 at 18:21

Note that a 2-regular graph is a disjoint union of cycles. Since you have a designated starting vertex $$v$$, you can disregard all cycles not containing $$v$$. Put differently, we can assume that the input graph is a single cycle (whose edges are labeled with zeros and ones).
Your current $$\Theta(\ell)$$ solution is optimal since even reading the input requires time linear in $$\ell$$, i.e., there exists no faster algorithm.
As a side note, the problem of finding an alternating 01-path is NP-hard for the general graph. Indeed, looking for such a path of length $$m = |E|$$ is equivalent to finding an alternating Hamiltonian path which is known to be NP-hard. This problem is easy for cycles of course.