我想我可能能够帮助你。你的问题可以很容易地转化为最长路径问题。在很长一段时间内，寻找长度为k的路径是非常困难的。即使k相对较小，比如说log(n)，人们仍然认为不能在多项式时间内解决。
基本思路：你重复着给图染色，希望你能偶然地染出长度为k的路径。这个概率非常小，但是如果你重复很多次，这个概率实际上变得非常大。
但首先，让我们假设在图中有一条有颜色的路径。"有颜色"是什么意思呢？有颜色意味着长度为k-1的路径（具有k个节点）用k种不同的颜色进行着色。如果你从一个颜色为1的节点v开始，你会怎么做？
你会查看你的邻居，看看他们是否和你有不同的颜色。如果是的话，你就把它们添加到一个叫做P(1)的集合中。你将继续与其中一个邻居保持联系，并查看它们是否有一个颜色，该颜色还没有出现在颜色集合中。只要你发现了你还没有见过的新颜色，或者你达到了k-1颜色，或者你看到其中一个节点有一个你已经看过的颜色，你就会不断这样做。在最后一种情况下，你会放弃任务，回到一切仍然很好的地方。
重要的是：我们染色节点。长度为i的路径有i + 1个节点和i条边。
更正式地说：
Let P i(v):= {S is element of ([k] choose i+1)| there exists a path, colored with the colors in S, which ends in v}
P并不是一条路径。P包含了一些我们称之为S的颜色集合。
在这种情况下，S不是一个数字。它是一个具有i + 1个不同颜色的基数子集。
例如：
P3(v)可以看作是{{绿色，红色，黑色，黄色}，{粉红色，橙色，灰色，黄色}，...}。注意到"yellow"出现了两次吗？如果我继续使用几个更多的子集，"yellow"将出现在每个集合中。为什么呢？因为它是我们的结束节点v的颜色！
因此，Pi(v)至少包含一个集合S，其中一个长度为i的路径被染成不同的颜色。这条路径以v结尾！
这意味着什么？
如果我们可以计算Pk-1(v)，并且集合不为空，则存在一条长度为k的路径。了不起。
但是我们如何计算
P k-1(v) 呢？
其实并不难：
如果我们想要计算
P i(v)，我们需要什么？
我们需要
P i-1(x). X。为什么？x 是
v 的邻居！ ---> g ----> y ---> o -----> x ------> v
假设
{green, yellow, orange, color of x} 是
P i-1(x) 的一个子集。我们称之为 R。
记得吗？
P i-1(x) 可以有很多不同的集合。它可以像这样：{{green, red, black, yellow}, {pink, orange, gray, yellow},{...}}!
那么 R 和 x 和 v 有什么关系呢？
R 是一组颜色，表示从 x 开始长度为 i-1 的彩色路径。如果顶点 v 是 x 的邻居，并且具有 R 中尚未出现的颜色，则可以将其添加到 R 中。但现在 R 已经增加了一种颜色。它的大小 |R| 现在是 i+2。
看起来这一定是 P i(v) 的新子集之一！为什么现在是 v？
好吧，我们已经通过一种颜色扩展了路径，因此最好将其保存在相应的集合中！
到目前为止，我们看到了什么：
- 你有一个集合 P i(v)，其中包含子集 S，它本身包含 i+1 种颜色（不要忘记 v）
- 如果你有一个集合 P k-1(v)，你就有一条长度为 k 的路径，然后你可以喝一杯啤酒。
- P i(v) 可以通过 P i-1(x) 计算，其中 x 是 v 的邻居！好处是你只需要检查 v 的颜色是否出现在 P i-1(x) 的一个子集中，我们称之为 R。
如何从头开始计算？
你从 P 0(v) 开始，这只是 v 的颜色。
然后对于 v 的每个邻居 x，你计算 P 1(v)。如果你记得 i-1 的事情，P 1(v) 就是 P 1-1(x)。P 0(x) 再次只是 x 的颜色。如果 x 和 v 的颜色不同，它们刚刚形成了第一个 P 1(v) 的子集！
然后通过计算 P 1(x) 来计算 P 2(v)，其中 P 1(x) 再次通过计算 P 0(y) 来计算，其中 y 是 x 的邻居。
只要我们还没有达到 P k-1(v)，就会继续进行。
至于 复杂性：这在 O(2^k km) 中运行。其中 m 是边的数量，k 是路径的长度。
现在我们能够使用这个算法在多项式时间内搜索长度为 k = log n 的路径。如果它比那更长，就不再是多项式了，不幸的是。
所以，现在我们有一个可以在多项式时间内找到“长”路径的算法。但是，等等。它只能在路径被着色的情况下做到这一点！
我不知道你住在哪里，但在我的世界里，默认情况下不会对图进行着色，特别是不同颜色的路径。
我们必须这样做。
用k种不同的颜色着色长度为k的路径的概率是多少？
用k种不同的颜色着色图形有k！种方法。但是用k种不同的颜色着色路径有k^k种不同的方法，其中它们可以多次出现。例如：用黄色=y和绿色=g，您有2！= 2个选项，其中颜色必须不同：（y，g）或（g，y）。当颜色不必不同时，您有k^k = 2^2 = 4个选项。 （y，y），（g，g）以及您已经看到的那些。
因此，Pr [路径着色为不同颜色] = k！/ k ^ k，大于e ^ -k，与1 / e ^ k相同。
所以你同意概率很小，对吧？
第一次成功的尝试数是多少？
这是一个几何分布，期望值为1/p = e ^ k。
因此，我们认为在e ^ k次尝试后，我们可以希望第一次拥有着色路径。有时会少，有时会多。
一个尝试的失败概率是1-e ^ -k，非常大。但是，如果我们说执行这个Te ^ k次，连续失败的概率变得非常小：（1-e ^ -k）^ Te ^ k <=（e ^ -e ^ -k）^ Te ^ k <= e ^ -T
因此，在Te ^ k次尝试之后，我们将成功的概率大于1-e ^ -T。而那非常小。
现在算法看起来怎么样？
1. 用k种不同的颜色随机着色图形。
2. 执行检查是否存在着色路径的算法。如果有，则返回它。如果没有，请继续。
3. 对Te ^ k次重复步骤1和2。（很有趣，相信我）。
实际上并不是这样。让计算机来做。
这种类型的算法称为Monte Carlo类型的随机化算法。
其运行时间为O（Te ^ k
2 ^ k km），而错误“没有路径（但实际上有一条）”的概率小于e ^ -T（再次非常小）。对于k = log n，这种随机化算法实现了多项式运行时间！
任何关于理解它的帮助都将不胜感激。