0
$\begingroup$

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.

$\endgroup$
1
  • 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, 2019 at 18:21

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\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$
    – integrator
    Dec 3, 2019 at 16:58

Your Answer

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