$\newcommand{\set}[1]{\{#1\}}$ $\newcommand{\inset}[2]{\{#1 \mid #2\}}$ $\newcommand{\name}[1]{\emph{#1}}$ $\newcommand{\size}[2][]{\left| #2^{#1} \right|}$ $\newcommand{\sig}[1]{\mathcal{#1}}$

Chordal Graph: Perfect elimination ordering

3回目のChordal Graph回です. 知識的にストックがあるのと,始めたばかりでやる気があるので,更新ペースがめちゃくちゃ早いです.

今回はPerfect elimination orderingについて説明します. Perfect elimination ordering (PEO) もchordal graphの重要で面白い性質の一つだと思います. chordal graphのいろんないい性質を見ていると,長さ4以上のサイクルには必ず弦があるという定義って結構狭いグラフクラスを 表しているのかなとか思いますね.

Perfect elimination ordering

Perfect elimination orderingとは頂点の順序付で,次の性質をみたす頂点の順序付のことです. どんな性質かというと,ある順序$\pi = (v_1, v_2, \dots, v_n)$の全ての$v_i$が,$G[V_i]$中でsimplicial vertexである とき,$\pi$をperfect elimination orderingと言います.ここで,$V_i$とは$\set{v_i, v_{i + 1}, \dots, v_n}$からなる頂点集合です. 図にするとこんな感じの順序付ですかね.simplicial vertexについてはこちらを見るとわかると思います.

f:id:chocobaby-aporo:20171107140822j:plain

こんな感じに順序付けると確かにどの頂点を見ても自分より頂点番号が大きい頂点からなる誘導部分グラフを考えると自分自身はsimplicial vertexになっていますね. PEOについてはこんな定理が知られています.

$G$がchordalである.$\iff$ $G$がPEOを持つ.

はい,またもや非自明感満載の定理が出てきました. とはいえ,実は前回のsimplicial vertexをうまいこと使うとこの定理も簡単に証明できます. ここでは$G$がchordalという条件を$A$,$G$がPerfect elimination orderingを持つという条件を$B$とします. それでは証明をしていきます. まずは$A \to B$から証明していきます. これは簡単で,前回にやった定理を使うと$G$はsimplicial vertexを1つは持つので,その頂点$v$を$G$から取り除きます. $G \setminus \set{v}$も同様にchordalなので,$G$がなくなるまでsimplicial vertexを選んで行けばPEOができます.

次に$B \to A$を証明します. ここで$\alpha = (u_1, \dots, u_n)$をPEOとします.ここで,$G$にサイクルがないと自明に$G$はchordalなので, $G$はサイクルを持っていると仮定し,その任意のサイクルを$C = (w_1, \dots, w_k)$とします. ここで,頂点番号を$\alpha$の順序で振り直したと考えます.$C$中の番号最小な頂点を$w_i$とすると, PEOの定義より,$w_i$の隣接頂点で,$w_i$より番号の大きな頂点たちはcliqueになっています. すると$C$は弦を持つことになります.また,その弦を含む$C$より短いサイクル$C'$を考えても 同様に頂点番号最小の頂点を持ってくると$C'$は弦を持ちます.これはサイクル長が3になるまで繰り返し 適用できるので,どんな長さ4以上のサイクルを持ってきても必ず弦を持ちます.したがって$G$は chordal graphになります.証明のイメージは下のような感じですかね?

f:id:chocobaby-aporo:20171104175426j:plain

多分次回はMaximum Cardinality Searchの話をして,次の回にClique Treeのことを書こうかと思います. Clique Treeは木幅とかとも関係がある概念だと(僕は)思っています.

雑談

  • この辺りは間違ったことを書いている可能性がありますので,変なこと書いていたらごめんなさい.

PEOの存在性もchordal graphの定義になることを紹介しました. 実はPEO繋がりでまだまだ面白い話はあってそれについて少し書いていこうと思います. この論文にも色々書いてありますが, 僕が分かる範囲で書いていこうと思います.

上記の論文中で適当に頂点の順序付をして,その順序付がPEOになるように辺をいくつか追加したグラフを$H$とすると, 元のグラフが$G$がchordalであることと$G$と$H$が一致するような順序付が存在することは 今回示した定理から同値な関係になることがわかります. しかも,PEOは実は線形時間で見つけることができるので,具体的な順序を見つけることも簡単にできます. この線形時間アルゴリズムは2つあって,一つがLexicographic breadth first search(Lex BFS)といい, もう一つが次の回で紹介するMaximum Cardinality Searchというアルゴリズムです.

ここで,この$H$が入力グラフ$G$と一致する順序を見つける問題をchordal graphでないグラフを入力とした場合を考えてみます. そうすると今回示した定理から当然そのような順序は存在しないので, ちょっと問題を変えてみて$G$に追加する辺の数が最小になるような順序付を見つける問題としてみましょう. 要は$H$の辺数から$G$の辺数を引いた値が最小になるようにしたい問題です. この問題はMinimum Fill-inと呼ばれているNP-完全問題になります. Minimum Fill-inは最適な木分解を求める問題と関連が深い問題のようです. (多分どっちかを解くアルゴリズムがあるとちょっと変更を加えるともう片方も解けるのだと思われる) すみません,どういう関連があるかは正確にわかっていない部分はあります. 一応こんな論文は出ていますね. 実際この論文では最適な木幅とMinimum Fill-inを計算するアルゴリズムを与えています. 当然多項式時間アルゴリズムではありませんが. このあたりの問題がにているなぁと感じる理由は後々書きます. もしかしたらそれまでにきちんと勉強して関連の部分を正確に書く日が来るかもしれません.