At the same time, the dynamic programming table at each vertex will have size 2 r (indexing on a bit vector of colors used per path), and the runtime of each trial will be proportional to this.
the running time for the necessary number of trials T r will be proportional to What r ≥ k should we choose to minimize this quantity?