Alternating Cycles Through Fixed Vertices in Edge-Colored Graphs

Abstract

In an edge-colored graph, a cycle is said to be alternating, if the successive edges in it differ in color. In this work, we consider the problem of finding alternating cycles through $p$ fixed vertices in $k$-edge-colored graphs, $k\ge 2$. We first prove that this problem is NP-Hard even for $p=2$ and $k=2$. Next, we prove efficient algorithms for $p=1$ and $k$ non-fixed, and also for $p=2$ and $k=2$, when we restrict ourselves to the case of $k$-edge-colored complete graphs.