v. Randomized Search: Color Coding and Random Walks

Randomized algorithms for search problems where a found answer is a certificate (one-sided error: “yes” is always right), so repetition drives the failure probability down exponentially.

Algorithm	Problem	Time	Error
color coding (Alon, Yuster, Zwick 1995)	simple path (or tree, cycle) with $k$ vertices	$O(e^k\cdot 2^{k}m)$ expected, i.e. $O((2e{)}^{k}m\log \frac{1}{\delta })$	misses with probability $\le \delta$
random walk for 2-SAT (Papadimitriou 1991)	2-SAT	$O(n^2)$ expected flips	$\le \frac{1}{2}$ per $2n^2$ flips; the linear SCC algorithm is better in practice: SCC and 2-SAT
Schöning’s walk (1999) for $k$-SAT	3-SAT	$O((4/3{)}^n\mathrm{poly}(n))$	exponential, but beats $2^n$
Karger, Karger–Stein	global minimum cut	$O(n^2{\log }^{3}n)$	Global Min Cut
random restarts of local search	MAX-SAT, partitioning	heuristic	Heuristic Optimization

Color coding

Colour the vertices randomly with $k$ colours and look only for colourful paths (all colours distinct): these are automatically simple, and they are found by a DP over subsets of colours instead of subsets of vertices. A fixed $k$-path is colourful with probability $\frac{k!}{k^k}\ge e^{-k}$, so about $e^k\ln \frac{1}{\delta }$ colourings suffice. Variants: $k$-cycles, trees of size $k$ (DP over the tree), weighted versions (minimum weight colourful path), and derandomization by perfect hash families.

// Is there a simple path with exactly k vertices? Monte Carlo with one-sided error; trials ~ e^k * ln(1/delta).
bool hasKPath(int n, const vector<vector<int>>& adj, int k, int trials, mt19937_64& rng) {
    if (k == 1) return n > 0;
    vector<int> col(n); vector<vector<char>> dp(1 << k, vector<char>(n));
    while (trials--) {
        for (auto& c : col) c = rng() % k;
        for (auto& row : dp) fill(all(row), 0);
        for (int v = 0; v < n; v++) dp[1 << col[v]][v] = 1;
        for (int mask = 1; mask < (1 << k); mask++) for (int v = 0; v < n; v++) if (dp[mask][v])
            for (int u : adj[v]) if (!(mask >> col[u] & 1)) dp[mask | 1 << col[u]][u] = 1;
        for (int v = 0; v < n; v++) if (dp[(1 << k) - 1][v]) return true;   // a colourful path is simple
    }
    return false;
}

Proof: color coding is correct and the trial count suffices

dp[mask][v] is 1 iff some path ends at $v$ whose vertices have pairwise distinct colours forming exactly mask (induction on the path length: extend by a neighbour with a new colour). A colourful path visits distinct colours, hence distinct vertices: it is simple, so “yes” answers are always right. If a $k$-vertex path $P$ exists, a random colouring makes it colourful with probability $\frac{k!}{k^k}$ (the $k^k$ colour sequences on $P$, of which $k!$ are permutations), and $k!\ge (k/e{)}^k$ gives $\ge e^{-k}$. After $T$ independent colourings the miss probability is $\le (1-e^{-k}{)}^T\le e^{-T{e}^{-k}}$, which is $\le \delta$ for $T=e^k\ln \frac{1}{\delta }$. Each trial costs $O(2^k(n+m))$. Checked against exhaustive DFS on random graphs with up to 10 vertices.

Random walks for satisfiability

// Clauses as vectors of literals: +(v+1) for x_v, -(v+1) for not x_v. Returns a satisfying assignment or empty.
vector<char> walkSAT(int n, const vector<vector<int>>& cls, ll restarts, ll stepsPerRestart, mt19937_64& rng) {
    auto sat = [&](const vector<int>& c, const vector<char>& x) { for (int l : c) if ((l > 0) == (bool)x[abs(l) - 1]) return true; return false; };
    for (ll r = 0; r < restarts; r++) {
        vector<char> x(n); for (auto& b : x) b = rng() & 1;              // random start
        for (ll s = 0; s <= stepsPerRestart; s++) {
            vector<int> bad; for (int i = 0; i < sz(cls); i++) if (!sat(cls[i], x)) bad.push_back(i);
            if (bad.empty()) return x;
            if (s == stepsPerRestart) break;
            const auto& c = cls[bad[rng() % sz(bad)]];
            int v = abs(c[rng() % sz(c)]) - 1; x[v] ^= 1;                    // flip a random literal of a violated clause
        }
    }
    return {};
}
// 2-SAT (Papadimitriou): walkSAT(n, cls, 50, 2 * n * n, rng)    -> failure <= 2^-50 if satisfiable
// 3-SAT (Schoening):     walkSAT(n, cls, c * pow(4/3., n), 3 * n, rng)

Proof: Papadimitriou's O(n^2) bound and Schöning's (4/3)^n

Fix a satisfying assignment $A^{\ast }$ and let $d$ be the number of variables where the current assignment differs from it. A violated clause is satisfied by $A^{\ast }$, so at least one of its literals disagrees with $A^{\ast }$ on its variable; flipping a uniformly random literal of the clause decreases $d$ with probability $\ge \frac{1}{2}$ for 2-clauses and $\ge \frac{1}{3}$ for 3-clauses (and otherwise increases it by 1).

2-SAT. $d$ performs a walk on $\{0,\dots ,n\}$ that moves down with probability at least $\frac{1}{2}$. The expected time to hit 0 from any start is at most that of the unbiased walk reflected at $n$, which is at most $n^2$ (the hitting time $h_j$ of the fair walk satisfies $h_j=1+\frac{h_{j-1}+h_{j+1}}{2}$, $h_0=0$, $h_n=1+h_{n-1}$, solved by $h_j=2nj-j^2\le n^2$). The walk can also stop earlier at another satisfying assignment. By Markov, $2n^2$ steps fail with probability $\le \frac{1}{2}$; $t$ restarts fail with probability $\le 2^{-t}$.

3-SAT. From distance $j$, one way to reach 0 within $3j$ steps is $j$ bad and $2j$ good steps: probability at least $\left(\genfrac{}{}{0ex}{}{3j}{j}\right)(\frac{1}{3}{)}^{2j}(\frac{2}{3}{)}^j$, and $\left(\genfrac{}{}{0ex}{}{3j}{j}\right)\ge \frac{1}{3j+1}(\frac{27}{4}{)}^j$ gives $\ge \frac{1}{3j+1}{2}^{-j}$. The starting distance is $\mathrm{Bin}(n,\frac{1}{2})$, so the success probability of one restart is at least $\frac{1}{3n+1}{\sum }_j\left(\genfrac{}{}{0ex}{}{n}{j}\right)2^{-n}{2}^{-j}=\frac{1}{3n+1}(\frac{3}{4}{)}^n$, and $O((4/3{)}^n\cdot n)$ restarts of $3n$ steps succeed with constant probability. Unsatisfiable formulas are always reported as such (one-sided). Checked against brute force on random 2-SAT and 3-SAT instances with up to 10 variables.

Related notes

• Randomized Algorithms
• Satisfiability
• Hamiltonian Paths and TSP (the exact $O(2^n{n}^2)$ DP)