Overcoming Browser Cookie Churn with Clustering

グラフアルゴリズムの話が面白かったので別項目で気になったことをいくつか書く。勉強会での発表者便所さんのスライドはこちら。
http://d.hatena.ne.jp/repose/20120407/1333809676

Interval Graphと貪欲彩色アルゴリズム

Interval Graphとは、実数区間を頂点とし、二区間に重複がある場合対応する頂点間に枝を引いたグラフである。論文中で関連する引用がされていないので恐らく超有名な話なのだろうがよく知らなかったので軽く調べた。

Interval Graphは次の貪欲アルゴリズムで最低の色数で彩色できる。

Input:頂点の集合
Output:頂点と色の対応

頂点を対応する区間の始まりの値でソートする
各頂点について順番に、
1. 既に色を塗った頂点で間に枝がないものが見つかればその色を塗る
2. 見つからなければ新しい色を塗る

計算量は、ソートに $O(|V|\log|V|)$ 、頂点のループに $O(|V|+|E|)$ で合計 $O(|V|log|V|+|E|)$ である。入力の時点ではどこに枝があるかは分かっていないが、ソートによってある頂点から出ている枝はその本数に比例した時間で見つけられるので、ここに由来する計算量は $O(|E|)$ で済むというのが上手いところである。最適性の直観的な根拠は、二頂点間に枝があるなら、ソートした順番でその二頂点の間にある頂点は二頂点の若い方との間に必ず枝があることによる。

実はInterval Graph $\subset$ Chordal Graph $\subset$ Perfectly Orderable Graph $\subset$ Perfect Graphであり、貪欲アルゴリズムの最適性はPerfectly Orderable Graphの性質である。グラフがPerfectly Orderableであるとは、頂点のある順序が、全ての誘導部分グラフ(よって自分自身も含む)について貪欲アルゴリズムが最適な解を見つけることを言う。そのような順序はperfect orderingとよばれ、次と同値である：任意の頂点と、その隣接頂点のうちその順序で先に来るものがクリークをなす。Interval Graphの頂点を区間の始まりでソートしたものはperfect orderingになっている(多分)。perfect orderingはChordal Graph一般について効率的に求めることができる。

論文中のAlgorithm2は上のアルゴリズム中で頂点に塗る色を、候補である枝を共有しない既存の色のうち、適当に決めた類似度が最大のものを選択するようにしたものである。ナイーブに実装すると色の候補数がバウンドされずスケールしないのでクッキー内の情報を利用して候補を狭めたり並列化したりしている。結構無理のあるヒューリスティクスだよなあと勉強会中でも話題になったが恐らくこうでもしないと本当に計算が終わらないのだと思う。計算時間と性能のトレードオフが知りたいところであるが論文中に定量的な言及はない。なお、候補のうちどの色を選んでも必要色数の最適性は崩れないが、Algorithm2では類似度がすべて一定値未満なら別の色を塗ることになっているのでこれは成り立たない。

参考：
http://en.wikipedia.org/wiki/Greedy_coloring
http://en.wikipedia.org/wiki/Chordal_graph

Theorem 1の証明のスケッチ

(後で書きます)