6
$\begingroup$

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!

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The solution is not meant to be randomized as it's not a part of the course syllabus ): $\endgroup$ – Noa Mar 8 at 12:11
  • 1
    $\begingroup$ I'm not sure what you mean. No randomness is needed to implement the dynamic programming. $\endgroup$ – Yuval Filmus Mar 8 at 12:43
  • 1
    $\begingroup$ @Noa Everything after the horizontal line is explaining why it's useful to be able to find cycles in which every vertex has a different colour. (Which is because it gives you a randomized algorithm for finding cycles in uncoloured graphs, which are the kind we're normally interested in.) $\endgroup$ – David Richerby Mar 10 at 17:19
  • $\begingroup$ Why a rand-alg, if we can just run a non-rand one which runs in poly time. We could just run Tarjan's algorithm ($O(|V|+|E|$) and check the results for cycles of length $k$. So unless the rand + DP approach manages to avoid the $|E|$ or $|V|$ in the runtime, I have a hard time seeing how this explanation really works. Maybe to find some other structure it makes sense, but at least for cycle I can't see it. Maybe, I just don't get it because you didn't provide any pseudocode or runtime analysis for the DP. I assume it makes sense and it's just me who doesn't get it since you got the upvotes.. $\endgroup$ – dingalapadum Mar 10 at 23:09
  • 1
    $\begingroup$ @dingalapadum, Tarjan's algorithm finds connected components, but although there will be a closed trail through the vertices of a connected component it doesn't a priori tell you much about simple cycles. It could be a useful preprocessing step on some graphs. $\endgroup$ – Peter Taylor Mar 11 at 9:34
1
$\begingroup$

The hint is in the question:

Let $k=\lfloor \log_2(n)\rfloor$

Why? Because then there are at most $n$ subsets of the colours...

$\endgroup$
  • $\begingroup$ This finds paths. Can it find cycles? $\endgroup$ – Yuval Filmus Mar 11 at 15:32
  • $\begingroup$ @YuvalFilmus, good question. I retract the claim, and apologise. $\endgroup$ – Peter Taylor Mar 11 at 23:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.