コグラフ

グラフ理論において、コグラフ、または補約可能グラフ、あるいはP ₄フリー グラフは、単一頂点グラフK _1から補集合と離散和集合によって生成できるグラフです。つまり、コグラフの族は、 K _{1 を}含み、補集合と離散和集合に関して閉じているグラフの最小のクラスです。

コグラフは1970年代から複数の著者によって独立に発見されており、初期の文献にはJung (1978)、Lerchs (1971)、Seinsche (1974)、およびSumner (1974)などがあります。コグラフはD*グラフ^[1] 、遺伝的デイシーグラフ(James C. Dacey Jr.の直交モジュラー格子に関する関連研究にちなんで)、^[2]、および2パリティグラフ^[3]とも呼ばれています。コグラフは、ラベル付きツリーで簡潔に表現できる分離和および補グラフ演算 を含む単純な構造分解を持ち、より一般的なグラフクラスでは困難な最大クリークを見つけるなどの多くの問題を効率的にアルゴリズム的に解決するために使用されています。

コグラフの特殊なケースには、完全グラフ、完全二部グラフ、クラスター グラフ、しきい値グラフなどがあります。また、コグラフは、距離遺伝グラフ、順列グラフ、比較可能性グラフ、完全グラフの特殊なケースです。

任意のコグラフは、次の規則を使用して構築できます。

1. 任意の単一頂点グラフはコグラフである。
2. が共字である場合、その補字も共字である。${\displaystyle G}$${\displaystyle {\overline {G}}}$
3. と が共グラフである場合、それらの互いに素な和である も共グラフです。${\displaystyle G}$${\displaystyle H}$${\displaystyle G\cup H}$

コグラフは、単一頂点グラフから始めて、これらの操作を使用して構築できるグラフとして定義できます。^[4] あるいは、補数操作を使用する代わりに、結合操作を使用することもできます。結合操作は、互いに素な和集合を形成し、 の頂点と の頂点のすべてのペアの間に辺を追加します。 ${\displaystyle G\cup H}$${\displaystyle G}$${\displaystyle H}$

コグラフにはいくつかの代替的な特徴付けが考えられます。その中には次のようなものがあります。

• コグラフとは、4つの頂点（したがって長さ3）のパス P _{4 を}誘導サブグラフとして含まないグラフです。つまり、グラフがコグラフである場合、任意の4つの頂点に対して、およびがグラフの辺である場合、またはの少なくとも1つも辺であるということです。^[4]${\displaystyle v_{1},v_{2},v_{3},v_{4}}$${\displaystyle \{v_{1},v_{2}\},\{v_{2},v_{3}\}}$${\displaystyle \{v_{3},v_{4}\}}$${\displaystyle \{v_{1},v_{3}\},\{v_{1},v_{4}\}}$${\displaystyle \{v_{2},v_{4}\}}$
• コグラフとは、その誘導サブグラフのすべてが、任意の最大クリークが単一の頂点で任意の最大独立集合と交差するという特性を持つグラフです。
• コグラフとは、すべての非自明な誘導サブグラフに、同じ近傍を持つ頂点が少なくとも 2 つあるグラフです。
• コグラフとは、接続されたすべての誘導サブグラフに切断された補グラフがあるグラフです。
• コグラフとは、連結された誘導サブグラフの直径が最大 2 であるグラフです。
• コグラフとは、接続されたすべてのコンポーネントが直径が最大 2 の距離遺伝グラフであるグラフです。
• コグラフはクリーク幅が最大2のグラフである。 ^[5]
• コグラフは直列-並列半順序の比較可能性グラフである。^[1]
• コグラフは分離可能な順列の順列グラフである。^[6]
• コグラフとは、その最小の弦完成がすべて自明に完全なグラフであるグラフである。^[7]
• コグラフは遺伝的に よく色付けされたグラフであり、あらゆる誘導サブグラフの貪欲な色付けが最適な数の色を使用するグラフである。 ^[8]
• グラフがコグラフであるためには、グラフのすべての頂点順序が完全順序である必要があります。これは、 P ₄がないということは、どの頂点順序にも完全順序を妨げるものが存在しないことを意味するためです。

コツリーは、内部ノードに 0 と 1 の番号が付けられたツリーです。すべてのコツリーT は、 Tの葉を頂点とするコグラフGを定義します。コグラフ G では、 Tの各ノードをルートとするサブツリーは、そのノードから派生する葉の集合によって定義される Gの誘導サブグラフに対応します。

• 単一のリーフ ノードで構成されるサブツリーは、単一の頂点を持つ誘導サブグラフに対応します。
• ラベル 0 のノードをルートとするサブツリーは、そのノードの子によって定義されたサブグラフの結合に対応します。
• ラベル 1 のノードをルートとするサブツリーは、そのノードの子によって定義されたサブグラフの結合に対応します。つまり、異なるサブツリーのリーフに対応する 2 つの頂点ごとに、結合を形成してエッジを追加します。あるいは、グラフ セットの結合は、各グラフを補完し、補完の結合を形成し、その結果得られる結合を補完することによって形成されると見なすことができます。

コツリーから形成されるコグラフを記述する同等の方法は、対応する葉の最低共通祖先に 1 のラベルが付けられている場合に限り、2 つの頂点がエッジで接続されるというものです。逆に、すべてのコグラフはコツリーによってこのように表現できます。このツリーの任意のルート リーフ パスのラベルが 0 と 1 の間で交互になるように要求する場合、この表現は一意です。^[4]

コグラフは線形時間で認識され、モジュラー分解、^[9]、 パーティション改良、^[10]、 LexBFS、^[11]、または分割分解^[12]を使用してコツリー表現が構築されます。コツリー表現が構築されると、多くの一般的なグラフ問題は、コツリー上の単純なボトムアップ計算によって解決できます。

たとえば、コグラフの最大クリークを見つけるには、コツリーのサブツリーによって表される各サブグラフの最大クリークをボトムアップの順序で計算します。ラベル 0 のノードの場合、最大クリークはそのノードの子に対して計算されたクリークの最大値です。ラベル 1 のノードの場合、最大クリークはそのノードの子に対して計算されたクリークの和集合であり、そのサイズは子のクリーク サイズの合計に等しくなります。したがって、コツリーの各ノードに格納されている値を交互に最大化して合計することで、最大クリーク サイズを計算でき、交互に最大化して和集合を取ることで、最大クリーク自体を構築できます。同様のボトムアップ ツリー計算により、コグラフのコツリー表現から、最大独立集合、頂点彩色数、最大クリーク カバー、およびハミルトン性 (つまり、ハミルトン閉路の存在) を線形時間で計算できます。^[4]コグラフはクリークの幅が制限されているため、クールセルの定理はコグラフ上のモナド的2階論理（MSO ₁）の任意の特性を線形時間でテストするために使用できます。 ^[13]

与えられたグラフがコグラフからk頂点離れているか、および/またはt辺離れているかをテストする問題は、固定パラメータで扱いやすい。^[14]グラフがコグラフにk辺削除可能かどうかの決定は、O ^* (2.415 ^k ) 時間で解決でき、^[15]コグラフにk辺編集可能かどうかの決定は、O ^* (4.612 ^k ) 時間で解決できる。^{[16]グラフから}k頂点を削除することによって、グラフの最大誘導コグラフサブグラフを見つけることができる場合、それは O ^* (3.30 ^k ) 時間で見つけることができる。^[15]

2つのコグラフが同型なのは、それらのコツリー（同じラベルを持つ2つの隣接する頂点がない標準形式）が同型な場合のみです。この同値性により、2つのコグラフのコツリーを構築し、ラベル付きツリーに対して線形時間同型性テストを適用することで、2つのコグラフが同型であるかどうかを線形時間で判断できます。^[4]

H がコグラフGの誘導サブグラフである場合、H自体がコグラフである。H のコツリーは、Gのコツリーからいくつかの葉を削除し、子を 1 つしか持たないノードを抑制することによって形成できる。クラスカルのツリー定理から、誘導サブグラフである関係はコグラフ上の準順序付けであることが分かる。[ 17 ^{]したがって、コグラフのサブファミリー (}平面コグラフなど) が誘導サブグラフ操作に対して閉じている場合、そのサブファミリーには有限数の禁止誘導サブグラフがある。計算的には、これは、与えられたグラフのコツリーに対してボトムアップ計算を使用して、これらの禁止サブグラフのいずれかが含まれているかどうかをテストすることにより、そのようなサブファミリーのメンバーシップを線形時間でテストできることを意味する。ただし、2 つのコグラフのサイズが両方とも可変である場合、そのうちの 1 つがもう 1 つの誘導サブグラフであるかどうかをテストすることはNP 完全である。^[18]

コグラフは、一度だけ読む関数を認識するアルゴリズムにおいて重要な役割を果たします。^[19]

いくつかのカウント問題は、入力がコグラフに制限されると扱いやすくなります。たとえば、コグラフ内のクリークの数や最大クリークの数をカウントする多項式時間アルゴリズムがあります。^[4]

n個の頂点を持つ連結コグラフの数（ n = 1, 2, 3, ...）は次のようになります。

1、1、2、5、12、33、90、261、766、2312、7068、21965、68954、...（OEISの配列A000669）

n > 1の場合、切断されたコグラフの数は同じです。これは、すべてのコグラフに対して、そのコグラフまたはその補グラフの 1 つだけが接続されているためです。

すべての完全グラフ K _nはコグラフであり、コツリーは単一の 1 ノードとn 個のリーフで構成されます。同様に、すべての完全二部グラフ K _{a , b}はコグラフです。そのコツリーは 1 ノードをルートとし、その 1 ノードには 0 ノードの子が 2 つあり、1 つはリーフの子を 1 つ持ち、もう 1 つはリーフの子をb持ちます。トゥラン グラフは、同じサイズの独立セットのファミリーを結合することで形成できます。したがって、これもコグラフであり、コツリーは 1 ノードをルートとし、各独立セットに対して子の 0 ノードを持ちます。

すべての閾値グラフはコグラフでもある。閾値グラフは、すべての前の頂点に接続されているか、どの頂点にも接続されていない1つの頂点を繰り返し追加することによって形成される。このような各操作は、コツリーを形成できる分離和または結合操作の1つである。 ^[20]

コグラフの特徴である、すべてのクリークと最大独立集合は空でない交差を持つという性質は、すべての誘導サブグラフにすべての最大クリークと交差する独立集合が含まれるという、強く完全なグラフの定義特性のより強いバージョンである。コグラフでは、すべての最大独立集合はすべての最大クリークと交差する。したがって、すべてのコグラフは強く完全である。^[21]

コグラフがP ₄フリーであるという事実は、コグラフが完全に順序付け可能であることを意味します。実際、コグラフのすべての頂点順序は完全な順序であり、これはさらに、最大クリークの検出と最小色付けが、任意の貪欲色付けを使用して、コツリー分解を必要とせずに線形時間で検出できることを意味します。

すべてのコグラフは距離遺伝グラフであり、コグラフ内のすべての誘導パスは最短パスであることを意味する。コグラフは、距離遺伝グラフの中でも、各連結成分の直径が最大でも 2 であるものとして特徴付けられる。すべてのコグラフは、コグラフを構成する分離和演算と結合演算を、部分順序の分離和演算と順序和演算に置き換えることによって得られる、直列並列半順序の比較可能性グラフでもある。強完全グラフ、完全に順序付け可能なグラフ、距離遺伝グラフ、および比較可能性グラフはすべて完全グラフであるため、コグラフも完全である。^[20]

• 「コグラフ グラフ」、グラフ クラス包含に関する情報システム
• ワイスタイン、エリック W.、「Cograph」、MathWorld