《パーフェクトグラフ》

【ぱーふぇくとぐらふ (perfect graph) 】

　1960年代初頭にベルジュ (C. Berge) は, パーフェクトグラフ (perfect graph) の概念やそれに関する予想を提案した. 予想の一つ「パーフェクトグラフの補グラフもパーフェクトである」は, 1972年にロバース(L. Lovász) によって解かれた. それよりも強い予想であるパーフェクトグラフ予想 (perfect graph conjecture) (後述) は近年ついに証明された~\cite{A-C-07+CRST}. パーフェクトグラフは半正定値計画問題の研究の源流の一つでもあり, 計算の複雑さの観点からも興味深いグラフのクラスである. パーフェクトグラフに関しては参考文献にあげた図書~\cite{A-C-07+RR,A-C-07+GLS}が詳しい.

　与えられたグラフ$G=(V,E)$に対して, 集合 $K \subseteq V$の任意の2頂点が隣接しているとき, $K$ を $G$ のクリーク (clique) とよぶ. 要素数最大のクリークを求める問題を $G$ に対する最大クリーク問題 (maximum clique problem) とよぶ. 最大クリークの大きさをクリーク数 (clique number) といい, $\omega(G)$とかく. さらに, 頂点集合上の整数値重み$w = (w_i \mid i \in V) \in Z^V$も導入し, 重みの総和を最大とするクリークを求める問題は次のような0-1整数計画問題

\begin{equation}\label{A-C-07+maxclique1}

  \begin{array}{lll}
   \mbox{max.}  & \sum_{i \in V} w_ix_i \\
   \mbox{s. t.} & x_i + x_j \leq 1 & ((i,j) \not\in E), \\
                & x_i \in \{0,1\}  & (i \in V),
  \end{array}

\end{equation}

に定式化でき, この最適目的関数値を $\omega(G,w)$ とかく. 明かに $\omega(G) = \omega(G,1)$ である. クリークと対称的な性質, 任意の2要素が互いに隣接しない集合 $S \subseteq V$ を $G$ の安定集合 (stable set), あるいは独立集合 (independent set) という. 任意のクリークと安定集合の共通部分は高々1頂点であることを利用すると問題(1)は安定集合全体のなす族${\cal S}$を用いて次のようにかける.

\begin{equation}\label{A-C-07+maxclique2}

  \begin{array}{lll}
   \mbox{max.}  & \sum_{i \in V} w_ix_i \\
   \mbox{s. t.} & \sum_{i\in S}x_i \leq 1 & (S \in {\cal S}), \\
                & x_i \in \{0,1\}  & (i \in V).
  \end{array}

\end{equation}

　グラフ$G=(V,E)$に対して, 隣接する頂点同士が異なる色になるような彩色の仕方を頂点彩色 (vertex coloring) あるいは単に彩色(coloring)とよぶ. 最小色数の頂点彩色を求める問題をグラフ彩色問題 (graph coloring problem) の一種である頂点彩色問題(vertex coloring problem) とよび, このときの最小色数を彩色数 (coloring number) といい, $\chi(G)$とかく.彩色において同色の頂点の集合は安定集合であり, 頂点彩色問題は, $V \subseteq S_1 \cup \cdots \cup S_\ell$となる安定集合の族$\{S_1,\cdots,S_\ell\}$で最小のものを求める問題とみなせる. さらに, 頂点集合上の重み$w = (w_i \mid i \in V) \in Z^V$も導入し

\begin{equation}\label{A-C-07+coloring}

  \begin{array}{lll}
   \mbox{min.}  & \sum_{S \in {\cal S}} y_S \\
   \mbox{s. t.} & \sum_{S \ni i}y_S \geq w_i & (i \in V), \\
                & y_S \in Z_+ & (S \in {\cal S}), 
  \end{array}

\end{equation}

という問題の最適目的関数値を $\chi(G,w)$ とかく(ただし${\cal S}$は$G$の安定集合全体のなす族, $Z_+$は非負整数全体を表す). 明かに $\chi(G,1)$ は彩色数 $\chi(G)$ と一致する. 問題 (3) の整数条件$y_S \in Z_+$を非負条件$y_S \geq 0$に置き換えた線形計画問題は, 問題 (2) の整数条件$x_i \in \{0,1\}$を非負条件 $x_i \geq 0$ で置き換えた線形計画問題の双対問題である. このことから次の関係が示せる.

\begin{equation}\label{A-C-07+inequ1}

\omega(G,w) \leq \chi(G,w), \quad 

\mbox{(特別な場合として)} \quad \omega(G) \leq \chi(G). \end{equation}

$\omega(G) \leq \chi(G)$ は任意の彩色でクリークの各頂点は異なる色に塗られることより明かであろう. 　一般のグラフに対する最大クリーク問題や頂点彩色問題のNP困難性が知られている. すなわち, 多くの研究者はこれらの問題に対する多項式時間解法は存在しないと信じている. 不等式 (4) の間に入る量で多項式時間で計算出来るものにロバース数 (Lovász number)がある. (本来の定義とは異なるが)ロバース数$\vartheta(G,w)$は

\begin{equation}\label{A-C-07+Lovasz}

   \vartheta(G,w) = \max \left\{ \bar{w}^{\top} B \bar{w} \; 
   \begin{array}{|l} 
     \mbox{$B$: 対称半正定値行列} \\
     B_{ij} = 0 \;((i,j) \in E) \\
     \sum_i B_{ii} = 1
   \end{array} \right\}, \quad
   \bar{w}= \left( \begin{array}{c}\sqrt{w_1}\\ \vdots\\ \sqrt{w_n}
               \end{array} \right) 

\end{equation}

と定義される. $G$の補グラフを$\overline{G}$と表すと,

\begin{equation}\label{A-C-07+inequ2}

\omega(G,w) \leq \vartheta(\overline{G},w) \leq \chi(G,w) 

\end{equation}

が成立する. グレッチェル (M. Grötschel), ロバースとシュライバー (A. Schrijver) は楕円体法でロバース数を多項式時間で求められることを示した. また (5) は半正定値計画問題なので, 半正定値計画問題に対する多項式時間解法でロバース数を求めることができる. 　グラフ$G=(V,E)$と$U \subseteq V$に対して, 頂点集合を$U$とし, 両端点が$U$に含まれる辺全体を辺集合とする$G$の部分グラフを, $U$に誘導される頂点誘導部分グラフとよぶ. $G$のすべての頂点誘導部分グラフ$G'$に対して $\omega(G') = \chi(G')$ を満たすグラフをパーフェクトグラフ (perfect graph) という. パーフェクトグラフを特徴付ける性質として次のようなものがある.

(a) 補グラフがパーフェクト,

(b) 任意の重みベクトル$w=(w_i \in Z_+ \mid i \in V)$に対して $\omega(G,w) = \chi(G,w)$,

(c) $G$のクリークの特性ベクトル全体の凸包が, 非負条件と問題 (2) の安定集合による不等式で表現できる,

(d) $G$の任意の頂点誘導部分グラフ$G'$に対して $\alpha(G')\cdot\omega(G') \geq |V(G')|$ が成立する, ただし$\alpha(G')$は$G'$の最大安定集合の要素数, $V(G')$は$G'$の頂点集合を表す,

(e) 頂点誘導部分グラフとして長さ5以上の奇ホールもその補グラフも含まない.

　(a)と(b)よりパーフェクトグラフに対して (6) は等号で成り立ち, 補グラフのロバース数を求めることで最大クリーク問題や頂点彩色問題が多項式時間で解けることが分かる. (c)は凸多面体を用いた特徴付けを与えている. (d)はロバースの与えた特徴付けで, この特徴付けより, 与えられたグラフがパーフェクトであるかの判定問題はco-NPに属する事が導かれる. この判定問題は多項式時間で解くことができる~\cite{A-C-07+CCLSV}. (e)がパーフェクトグラフ予想と呼ばれていたものであり, 論文~\cite{A-C-07+CRST}において証明され, 現在は強パーフェクトグラフ定理 (Strong Perfect Graph Theorem) と呼ばれる.

---

参考文献

[1] J. L. Ram{\'i}rez-Alfons{\'i}n and B. A. Reed, eds., Perfect Graphs, John Wiley & Sons, 2001.

[2] M. Chudnovsky, G. Cornu{\'e}jols, X. Liu, P. Seymour and K. Vuskovic, "Recognizing Berge Graphs," Combinatorica, 25 (2005), 143-186.

[3] M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, "The Strong Perfect Graph Theorem," Ann. of Math., 164 (2006), 51-229.

[4] M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, 1988.