patternMinor
Find a $\log_2(|V|)$ long cycle where each node is of different color
Viewed 0 times
cycleeachnodewherecolorlonglog_2differentfind
Problem
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!
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!
Solution
The idea is to use dynamic programming. For every pair of vertices $x,y$ and subset $S$ of colors, you determine whether there is a path from $x$ to $y$ of length $|S|$ (measured in vertices) which uses all colors in $S$, each of them exactly once.
What is this good for? Usually our graphs are not colored. The idea of color coding is that finding cycles (and other structures) is much easier if vertices or edges are colored: instead of having to remember all vertices visited in the cycle being constructed, it suffices to remember the colors encountered. Therefore we need to introduce the colors into our graph. How do we do that? In the simplest possible way: randomly.
Suppose that we want to find a directed cycle of length $k = \ln n$ in a directed graph. We color the vertices of the graph randomly with $k$ colors. If there is a directed cycle of length $k$, then the probability that all of its vertices are colored with different colors is $k!/k^k \approx e^{-k} = 1/n$. Therefore if we try (say) $n\log n$ different random colorings, then it is highly likely that one of these colorings would color the vertices of the cycle with different colors. When that happens, the dynamic programming algorithm outlined above will find the cycle. Conversely, if there is no directed cycle of length $k$, then no coloring would confuse us.
All in all, we obtain a randomized algorithm, running in polynomial time, that finds a cycle of length $k$, if one exists, with high probability.
What is this good for? Usually our graphs are not colored. The idea of color coding is that finding cycles (and other structures) is much easier if vertices or edges are colored: instead of having to remember all vertices visited in the cycle being constructed, it suffices to remember the colors encountered. Therefore we need to introduce the colors into our graph. How do we do that? In the simplest possible way: randomly.
Suppose that we want to find a directed cycle of length $k = \ln n$ in a directed graph. We color the vertices of the graph randomly with $k$ colors. If there is a directed cycle of length $k$, then the probability that all of its vertices are colored with different colors is $k!/k^k \approx e^{-k} = 1/n$. Therefore if we try (say) $n\log n$ different random colorings, then it is highly likely that one of these colorings would color the vertices of the cycle with different colors. When that happens, the dynamic programming algorithm outlined above will find the cycle. Conversely, if there is no directed cycle of length $k$, then no coloring would confuse us.
All in all, we obtain a randomized algorithm, running in polynomial time, that finds a cycle of length $k$, if one exists, with high probability.
Context
StackExchange Computer Science Q#105320, answer score: 7
Revisions (0)
No revisions yet.