1. 概要

本記事では，Color-Coding という手法について解説します．

Color-Coding とは $k$ 個のものを選ぶというような存在判定問題や最適化問題において，それぞれのものにランダムな色を割り当てるという手法です．特に，比較的小さな $k$ について「ちょうど $k$ 種類のものを $1$ 度ずつ使う必要がある」という制約がある最適化問題で強力です．学術的にはグラフから $k$ 頂点のパスやサイクル，その他の種類の部分グラフを検出するアルゴリズムとして提案された乱択アルゴリズムです（文献 1）．

本記事ではそのうちでも最も簡潔な，パスの検出という問題を通して Color-Coding について解説します．

2. 前提知識

グラフの用語および，初歩的な dp を仮定します．

3. Color-Coding によるパスの検出

3.1. 問題

【問題 1】

$G$ を $N$ 頂点 $M$ 辺の単純無向グラフとします．$k$ を正整数とします．$G$ に $k$ 頂点のパス（長さ $k-1$ のパス）が存在するか否かを判定してください．

ほとんどパスの定義そのものですが，説明のため，次の形に言い換えておきます．

【問題 1 の言い換え】

$G$ を $N$ 頂点 $M$ 辺の単純無向グラフとします．$k$ を正整数とします．頂点列 $(v_1,v_2,\ldots,v_k)$ であって，以下の条件を満たすものが存在するか否かを判定してください．

$G$ のウォークである．つまり各 $i$ （$1\leq i\leq k-1$）に対して $v_i,v_{i+1}$ は $G$ において隣接する．
$i\neq j$ ならば $v_i\neq v_j$ が成り立つ．

3.2. Color-Coding による解法

Color-Coding は頂点にランダムに色を割り当てることで，【問題 1】を，次の【問題 2】や【問題 3】を繰り返し解く問題へと変換する手法です．

【問題 2】

$G$ を $N$ 頂点 $M$ 辺の単純無向グラフとします．$k$ を正整数とします．また各頂点には $1$ 以上 $k$ 以下の整数の色が割り当てられています．

頂点列 $(v_1,v_2,\ldots,v_k)$ であって，以下の条件を満たすものが存在するか否かを判定してください．

$G$ のウォークである．つまり各 $i$ （$1\leq i\leq k-1$）に対して $v_i,v_{i+1}$ は $G$ において隣接する．
$v_i$ の色は $i$ である．

【問題 3】

$G$ を $N$ 頂点 $M$ 辺の単純無向グラフとします．$k$ を正整数とします．また各頂点には $1$ 以上 $k$ 以下の整数の色が割り当てられています．

頂点列 $(v_1,v_2,\ldots,v_k)$ であって，以下の条件を満たすものが存在するか否かを判定してください．

$G$ のウォークである．つまり各 $i$ （$1\leq i\leq k-1$）に対して $v_i,v_{i+1}$ は $G$ において隣接する．
$v_1,v_2,\ldots,v_k$ の色は相異なる．

Color-Coding による【問題 1】の解法は，おおよそ次のようなものです．

以下を十分な回数（後述）反復する．
- まず各頂点に $1$ 以上 $k$ 以下の色をランダムに割り当てる．
- 【問題 2】あるいは【問題 3】を解く．条件を満たす頂点列が見つかったら，それは【問題 1】の解でもあるので，これを出力し，終了する．
十分な回数反復しても解が見つからなかったら，解なしとして終了する．

この解法の過程で【問題 2】あるいは【問題 3】を解く必要があります．これは Color-Coding という手法とは直接は関係がないので，最小限の解説にとどめます．

【問題 2】の解法

次のような dp で解くことができます．

$\mathrm{dp}[v]$ を次の bool 値として定義する．
- $v$ を終点とするウォーク $(v_1,v_2,\ldots,v_i)$ （$v_i=v$）であって，任意の $j$ （$1\leq j\leq i$）に対して $v_j$ の色が $j$ であるものが存在する．
$i=1,2,\ldots,k$ について順に，色 $i$ の頂点 $v$ に対する $\mathrm{dp}[v]$ を求めていく．

適切に実装すれば，$\mathrm{O}(k+N+M)$ 時間で【問題 2】を解くことができます．

【問題 3】の解法

部分集合を状態とする dp （bit dp）で解くことができます．つまり，

$\lbrace 1,\ldots,k\rbrace$ の部分集合 $s$ および，頂点 $v$ に対して， $\mathrm{dp}[s][v]$ を次の bool 値として定義する．
- $v$ を終点とするウォーク $(v_1,v_2,\ldots,v_i)$ （$v_i=v$）であって，$v_1,v_2,\ldots,v_i$ の色が相異なり，これらに現れた色の集合が $s$ に等しいものが存在する．
$s$ について昇順に $\mathrm{dp}[s][v]$ を求めていく．

とすればよいです．適切に実装すれば，$\mathrm{O}(2 ^ k(N+M))$ 時間で【問題 3】を解くことができます．

なお，以下の解説を理解する上では，【問題 3】の解法が理解できなくとも，【問題 2】の解法が理解できていれば十分です．

3.3. 試行回数と成功確率

各頂点に $1$ 以上 $k$ 以下の色をランダムに割り当てたとき，次が成り立つことが分かります．

【問題 1】が解を持つとき，確率 $\dfrac{1}{k ^ k}$ 以上で【問題 2】に解が存在する．
【問題 1】が解を持つとき，確率 $\dfrac{k!}{k ^ k}$ 以上で【問題 3】に解が存在する．

これは，【問題 1】の解をひとつ固定した上で，そのひとつの解が【問題 2】や【問題 3】で検出できる確率を考えると分かります．（なお，確率いくつ以上という下からの評価になっているのは，【問題 1】が複数の解を持つときのことを考慮しているからです．また【問題 2】で $k\geq 2$ の場合には，頂点の並び順が逆順である場合を考えることで，確率を $\dfrac{2}{k ^ k}$ 以上と見積もることもできます．）

このことから 3.2 節のアルゴリズムの試行回数と成功確率の関係を調べることができます．成功確率 $p$ の試行を $n$ 回反復するとき， $1$ 度も成功しないという失敗確率は $(1-p) ^ n$ です．例えば $k=5$ として試行回数と失敗確率の関係をプログラムで調べると，次の表のようになります．

なお，このような見積もりでは自然対数 $e$ に関する知識も役に立ちます．

自然対数の底 $e$ とは

$e=\lim_{n\to \infty}\left(1+\dfrac{1}{n}\right) ^ {n}$ を自然対数の底や，ネイピア数などといいます．$e=2.71828182845\cdots$ が知られています．$\lim_{x\to 0}(1+x) ^ {1/x}=e$ が成り立ち，特に $p$ が $0$ に近い正実数であるとき $(1-p) ^ {1/p}$ はおよそ $e ^ {-1}=0.3678944\cdots$ になります．

$p$ が小さいとき，$n/p$ 回程度の試行で失敗確率 $e ^ {-n}$ となります．このことから，目標の失敗確率に対してどのように試行回数 $n$ を定めればよいかが分かります．

また，試行回数（実行時間）を $2$ 倍，$3$ 倍と増やすにつれて，失敗確率は $2$ 乗，$3$ 乗という指数の関係で減少することにも注意してください．ある実行時間での失敗確率が $\frac{1}{10}$ であるとき，その実行時間を $10$ 倍，$100$ 倍とすると失敗確率が $\frac{1}{10^{10}}$ や $\frac{1}{10^{100}}$ であるようなアルゴリズムになります．

参考：乱択アルゴリズムの失敗確率と競技プログラミング

競技プログラミングでは，$100$ 個程度（多くとも数百個）の入力に正解すれば正答となることが一般的です．そのため，失敗確率 $0.01$ から $0.001$ 程度のアルゴリズムであれば正答できることが多いでしょう．ただし，マルチテストケース形式などでは，より低い失敗確率が求められるので注意が必要です．

ただし出題側は乱数の当たり外れの結果への影響を小さくするために，（特にコンテスト後にシステムテストを行う形式のコンテストである場合には）より低い失敗確率のアルゴリズムの実装を想定するのが望ましいでしょう．

【問題 3】を利用する解法では，試行 $1$ 回あたりの成功確率は $\frac{k!}{k ^ k}$ で，また $1$ 回の試行あたりの計算量が $\mathrm{O}(2 ^ k(N+M))$ 時間でした．このことから，次の定理が得られます．

【定理 4】

$\varepsilon > 0$ を正実数とするとき，Color-Coding によって【問題 1】を次の成功確率と時間計算量で解くことができる．

成功確率 $(1-\varepsilon)$ 以上．
時間計算量 $\mathrm{O}\left(\dfrac{(2k) ^ k}{k!}(N+M)\log \varepsilon ^ {-1}\right)$．

3.4. $k$ 頂点のパスに関する最適化

上に挙げた解法は，ほとんどそのまま次のような最適化（最大化や最小化）の問題の解法になります．

【問題 5】

$G$ を $N$ 頂点 $M$ 辺の単純無向グラフとします．さらに，各辺には重みが定まっているとします．$k$ を正整数とします．

$G$ に $k$ 頂点のパス（長さ $k-1$ のパス）であって，通る辺の重みの総和が最大であるものを求めてください（そのようなパスが存在しなければそのことを報告してください）．

頂点にランダムな色を割り当てた上で【問題 2】や【問題 3】のような最適化問題を解くことを十分な回数反復し，それらの解の最大値を出力する，というようにすればよいです．成功確率の評価についても【問題 1】と同様です．この方法で最適解が見つかるのは，最適解を与えるパスが一度以上探索対象になるときだからです．

3.5. 発展的な話題

本記事では，$k$ 頂点のパスの検出あるいは最適化という問題を通して，Color-Coding という手法を解説しました．ここで，$k$ 頂点のパスの検出に関する他の話題について少し触れておきます．

【問題 1】や【問題 5】は，一般には NP 困難であることが知られています．本記事のアルゴリズムは，これらの問題には，$k$ を定数と見なせば $N,M$ については多項式時間の計算量で解けるというもので，$k$ をパラメータとする FPT アルゴリズム（Fixed Parameter Tractable Algorithm）として有名です．

【定理 4】において $k$ の関係する部分 $\dfrac{(2k) ^ k}{k!}$ を，$\dfrac{(2k) ^ k}{k!}=\mathrm{O} ^ *\left((2e) ^ k\right)$ と評価することもできます．この指数を改良するという研究も行われています．

例えば，本記事の手法をほとんどそのまま拡張して，頂点に割り当てる色の種類数を $k$ よりも少し大きくとることで，【問題 1】はより高速な計算量 $\mathrm{O} ^ *(4.32 ^ k\cdot (N+M)\log\varepsilon ^ {-1})$ 時間で解くことができることが分かります（文献 4）．

なお，Color-Coding とは全く異なる方向の乱択アルゴリズムにより計算量を $\mathrm{O} ^ * (2 ^ k(N+M)\log \varepsilon ^ {-1})$ に改良できることも知られています（文献 5）．

また，本記事の解法はいくら反復を増やしても，解の正しさを確率的にしか保証できない点が気になった方もいると思います．そこで，乱択をやめて $k$ 個の色の割り当てを戦略的に反復することで，すべてのパスが【問題 2】や【問題 3】の解として発見できるようにするという方法も考えられます．このような方法は脱乱択化（derandomization）と呼ばれます．

脱乱択化によって解の正しさを保証するための反復回数は，乱択する場合の解法より大きくなりますが，$N$ に対する依存度は $\mathrm{O}(\log N)$ 程度に抑えられることが知られています（文献 1）．

4. 関連問題

本記事では，$k$ 頂点のパスの検出（最適化）という問題に限定して，Color-Coding という手法を解説しました．他にも

$k$ 個のもの $a_1, a_2, \ldots, a_k$ を選ぶというタイプの最適化問題．
ただし各 $a_i$ が相異なる，あるいは各 $a_i$ の種類が異なるという制約がある．

というような最適化問題について，Color-Coding が有効に働くことがあります．

問題について

1 は本記事の手法がおおよそそのまま適用できる問題です．

2 は $2$ つの異なる種類を用いるという制約での最適化問題で，Color-Coding が適用できることがコンテスト後に少し話題になりました．このような問題では $2$ 種類分について最適な状態を保持するという手法が簡潔で計算量も良いので，やや特殊な解法といえますが，Color-Coding も選択肢として持っておくと，場合によっては実装の簡略化に役に立つかもしれません．

3，4，5 も相異なる $k$ 種のものを選ぶというタイプの最適化問題で，Color-Coding を使うことでかなり解きやすくなります．ただし 5 はこの中でも Color-Coding を使ったあとの問題でも少し考察が必要で，また制約もタイトなのでやや難易度が高いです．

6 も Color-Coding で少し考察を簡略化できますが，色の塗り方や色を塗ったあとの解法によっては，実行時間超過への注意が必要になります．

5. まとめ

本記事ではパスの検出という問題を通して Color-Coding について解説しました．

Color-Coding は，各要素に色を割り当てることで，「相異なる $k$ 種類の要素を使う」というようなタイプの制約がある最適化問題を，はじめからものの種類が $k$ 種類である場合に帰着できるという手法です．ある程度の確率で正しく解ける解法を何度も反復すれば正しい解が求まるという乱択アルゴリズム特有の解法も面白いところだと思います．

また，Color-Coding は学術的にはグラフから $k$ 頂点のパスやサイクル，その他の種類の部分グラフを検出するアルゴリズムとして提案されたアルゴリズムですが，その用途は部分グラフ検出だけにとどまらないことが関連問題からも分かると思います．

6. 参考文献

Noga Alon, Raphael Yuster, Uri Zwick．Color-Coding．Journal of the ACM．Vol. 42．No. 4．pp. 844–856．1995．DOI: 10.1145/210332.210337．https://doi.org/10.1145/210332.210337．
Wikipedia．Color-Coding．https://en.wikipedia.org/wiki/Color-Coding．（閲覧日: 2026-03-31）．
Wikipedia．Longest path problem．https://en.wikipedia.org/wiki/Longest_path_problem．（閲覧日: 2026-03-31）．
Falk Hüffner, Sebastian Wernicke, Thomas Zichner．Algorithm Engineering for Color-Coding with Applications to Signaling Pathway Detection．Algorithmica．Vol. 52．No. 2．pp. 114–132．2008．DOI: 10.1007/s00453-007-9008-7．https://doi.org/10.1007/s00453-007-9008-7．
Ryan Williams．Finding paths of length k in O*(2^k) time．Information Processing Letters．Vol. 109．No. 6．pp. 315–318．2009．DOI: 10.1016/j.ipl.2008.11.004．https://doi.org/10.1016/j.ipl.2008.11.004．
Yuichi Yosida．乱択アルゴリズム紹介(Color-Coding)．Preferred Networks Tech Blog．https://tech.preferred.jp/ja/blog/color-Coding/．（閲覧日: 2026-03-31）．
清水伸高．color-codingと脱乱択化．Le Algorithm．https://lealgorithm.blogspot.com/2018/11/color-coding.html．（閲覧日: 2026-03-31）．

トップページ：AtCoder Algorithm Lectures