2020年3月16日月曜日

CodeChef March Challenge 2020 - Egg-free DAG

egg-free DAGが作れるためには明らかにchordal graphでないといけない。逆にchordal graphなら、perfect elimination orderingにしたがってDAGを作れば勝手にegg-freeになる。

以下は必要なアルゴリズムについてのメモ。

与えられた頂点の順列がperfect elimination ordering (PEO)か判定する

https://www.cse.iitd.ac.in/~naveen/courses/CSL851/uwaterloo.pdf に疑似コードが載っている。ハッシュテーブルを使えば期待線形時間の実装は難しくない。できればハッシュテーブルなしで線形にしたかったけれど、やり方を思いつかなかった。

Maximum Cardinality Search

chordal graphに対してPEOを求めるアルゴリズム。正確には、グラフに対してなんらかの頂点の順列を出力し、入力がchordal graphであればそれが必ずPEOになっているアルゴリズム。結果を上の判定アルゴリズムで調べれば、chordal graphかどうかも同時にわかることになる。

An introduction to chordal graphs and clique treesの疑似コードより:

V := {0, 1, ..., N-1}
L = {}
result = []
for i from N-1 downto 0:
  find v in V s.t. |adj(v) ⋂ L|が最大
  result[i] = v
  L := L + {v}
  V := V - {v}

これを実装するのがけっこう難しかった。$\log N$がついていいなら優先度変更可能なヒープを使うのがいちばん簡単？

V := 頂点0, 1, ..., N-1を優先度0として挿入したヒープ
L = {}
result = []
for i from N-1 downto 0:
   v := V.pop()
   result[i] = v
   for w in vの隣接頂点:
     wがLに含まれていればwの優先度を+1する

しかし、優先度の範囲が$0 \sim N-1$なので、頑張れば配列の操作だけで線形にできる……はずなのだが、簡潔な方法が思いつかなかった。けっきょく、双方向リストを二次元的に持ってdancing linksのようなことをして優先度の変更とポップを${O}(1)$にした。[1] 自分の実装はここにある。

Editorialはmaximum cardinality searchではなくlex. BFSに言及していたけれど、これはこれでけっこう大変そうに見える。

性質を調べてググって特徴付けを理解してアルゴリズムを実装して……みたいな段取りに3日かけてしまった。

  1. 正統な方法はTarjan, Yannakakis(1984)に書いてあるらしいのだが、買えなかった…… ↩︎

投稿者