Alternating Cycles Through Fixed Vertices in Edge-Colored Graphs

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 \geq 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.