Here’s a question from an algorithms exam by Prof. Noga Alon that I just can’t wrap my head around.
Let $ G=(V,E)$ be a directed graph where $ |V|=n$ . Let $ k=\lfloor \log_2(n)\rfloor$ . Each node in the graph is in one of $ k$ colors. Give an efficient algorithm to determine if there exists a simple cycle of length $ k$ in the graph where each node has a different color.
I really don’t know where to start with this. I thought about breaking the graph into subsets of nodes of each color and having multiple copies of each subsets in order to force a color change with every edge we traverse but I couldn’t get this to work. Any hint is appreciated!