Given a directed graph whose nodes are colored with k=log(|V|) colors, determine whether a cycle of length k containing every color exists

Question

Given a directed graph $G=(V,E)$, such that the nodes are colored with $k=\lfloor{log_2(n)\rfloor}$ colors. Describe an algorithm that determines whether a cycle of length $k$ containing every color exists.

My idea was to use dynamic programming like so: I denote the colors as $C=\{1,2,...,k\}$. For every pair of vertices $x,y$ and subset $S \subseteq C$, $dp[x,y,S]=true$ if there exists a path from $x$ to $y$ of length $|S|$ that uses all the colors in $S$.

We start building the table by $dp[x,x,\{color(x)\}]=true$ for every $x\in V$ where $color(x)$ denotes the color of vertex $x$. And then, for every pair of vertices $x,y$ and subset $S$:

If $dp[x,y,S]$ is not yet filled, then we go over every neighbor $z$ of $x$: If $color(z)\in S$ then let $S'=S\backslash\{color(z)\}$, and we check whether $dp[y,z,S']=true$. If both of the above conditions are met for some neighbor $z$, then $dp[x,y,S]=true$.

This solution seems like it works to me, but my issue is efficiency. It seems like this problem can be solved in $O(n^3)$ time, but this solution takes $O(n^4)$ time.

Answer 1

Continuing from the comment.

A classic observation is that $\sum_{v \in V} \deg(v) = 2m = O(m)$.

This means that when you run two for loops:

for v in V:
    for u in N(v):
        counter = counter + 1

the inner instruction happens exactly $2m$ times (ie you visit each edge twice).

So, yes, while your DP table has $n^2 2^k$ many cells and each cell takes time $O(n)$ time to compute, a more careful analysis shows that you can compute it all in $O(n^2 m)$ time, simply because you don't use $\Theta(n)$ time to fill in the cell of a specific vertex $v$, but $\Theta(\deg(v))$.

I encourage you to implement it, in eg. Python, and observe that the inner loop runs precisely $2 n m 2^k$ times.