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.

  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ In the case of a walk, it isn't immediately clear (or at least clear to me) that there is a linear-time algorithm. Of course you are right that if the OP's algorithm is correct then it is optimal. $\endgroup$ – eru-cs Dec 3 '19 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.