スキューパーティション

グラフ理論において、グラフの斜め分割とは、グラフの頂点を 2 つの部分集合に分割することであり、2 つの部分集合のうちの 1 つによって形成される誘導部分グラフは切断され、もう 1 つの部分集合によって形成される誘導部分グラフは切断されたグラフの補グラフとなります。斜め分割は、完全グラフの理論において重要な役割を果たします。

グラフの歪曲分割とは、グラフの頂点を 2 つのサブセットとに分割することです 。この場合、誘導サブグラフは切断されており、誘導サブグラフは切断されたグラフ (相互に切断されている) の補集合となります。同様に、グラフの歪曲分割は、の頂点を4 つのサブセット 、、、および に分割することで記述できます。この場合、 からへの辺は存在せず、 からへのすべての可能な辺が存在します。このような分割では、誘導サブグラフおよび はそれぞれ切断され、相互に切断されているため、および を取ることができます。 ${\displaystyle G}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle G[X]}$${\displaystyle G[Y]}$${\displaystyle G}$${\displaystyle G}$${\displaystyle A}$${\displaystyle B}$${\displaystyle C}$${\displaystyle D}$${\displaystyle A}$${\displaystyle B}$${\displaystyle C}$${\displaystyle D}$${\displaystyle G[A\cup B]}$${\displaystyle G[C\cup D]}$${\displaystyle X=A\cup B}$${\displaystyle Y=C\cup D}$

4 つ以上の頂点を持つすべてのパス グラフには、歪んだ分割があります。歪んだ分割では、共切断セットはパスの内部エッジの 1 つであり、切断セットはこのエッジの両側の頂点で構成されます。ただし、任意の長さのサイクル グラフでは歪んだ分割を持つことはできません。サイクルのどのサブセットをセットとして選択したとしても、補完セットには同じ数の接続コンポーネントが含まれるため、が切断され、 が共切断されること はありません。${\displaystyle Y}$${\displaystyle X}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$

グラフに歪んだ分割がある場合、その補グラフにも歪んだ分割があります。たとえば、パス グラフの補グラフには歪んだ分割がありますが、サイクル グラフの補グラフには歪んだ分割がありません。

グラフ自体が不連続である場合、3つの単純な例外（空のグラフ、1つの辺と3つの頂点を持つグラフ、または4つの頂点の完全マッチング）を除いて、そのグラフは歪んだ分割を持ちます。この分割では、分割の共不連続側は単一の辺の端点で構成され、不連続側は他のすべての頂点で構成されます。同じ理由で、グラフの補グラフが不連続である場合、対応する3つの例外セットを除いて、歪んだ分割を持つ必要があります。^[1]

グラフに、 1 つ以上の頂点を持つクリーク セパレータ(削除すると残りの頂点が切断されるクリーク) がある場合、クリークと残りの頂点への分割は、歪んだ分割を形成します。1 つの頂点を持つクリーク カットセットは、連結点です。そのような頂点が存在する場合、少数の単純な例外を除いて、共切断側がこの頂点とその隣接する頂点の 1 つで構成される歪んだ分割が存在します。^[1]

グラフ内のスターカットセットは、頂点セパレーターの 1 つが他のすべての頂点に隣接している頂点セパレーターです。すべてのクリークセパレーターはスターカットセットです。必然的に、スターカットセット (複数の頂点を持つ) を持つグラフには、共切断されたサブグラフがスターカットセット内の頂点で構成され、切断されたサブグラフが残りのすべての頂点で構成されるスキューパーティションがあります。^[1]${\displaystyle G}$

モジュール（または同次集合）は、の頂点の非自明な部分集合であり、に含まれないすべての頂点について、 のすべての頂点に隣接しているか、 のどの頂点にも隣接していないかのいずれかである。グラフにモジュールがあり、その外側に のすべての頂点に隣接する頂点と、どの頂点にも隣接していない頂点の両方が存在する場合、 にはモジュール内の 1 つの頂点とモジュール外のその隣接頂点からなる星型カットセットが存在する。一方、これら 2 つの部分集合のいずれかが空であるモジュールが存在する場合、グラフは非接続または相互非接続であり、この場合も（3 つの単純な例外を除いて）歪んだカットセットが存在する。^[1]${\displaystyle H}$${\displaystyle G}$${\displaystyle v}$${\displaystyle H}$${\displaystyle v}$${\displaystyle H}$${\displaystyle G}$${\displaystyle H}$${\displaystyle H}$${\displaystyle G}$

歪分割は、パーフェクトグラフに関連して、Chvátal (1985) によって導入されました。Chvátal は、最小不完全グラフはスターカットセットを持たないことを証明しました。当然のことながら、切断されたグラフは最小不完全ではあり得ず、クリークセパレータまたはモジュールを持つグラフは最小不完全ではあり得ないことも知られていました。^[2] Claude Bergeは、1960 年代初頭に、パーフェクトグラフは Berge グラフと同じであり、誘導された奇数サイクル (長さ 5 以上) またはその補集合を持たないグラフであり、(サイクルとその補集合には歪分割がないため) 最小の非 Berge グラフには歪分割が存在しないと予想しました。これらの結果に動機づけられて、Chvátal は、最小不完全グラフには歪分割が存在しないと予想しました。何人かの著者がこの予想の特殊なケースを証明しましたが、何年も未解決のままでした。^[3]

歪分割は、Chudnovsky ら (2006) が、 Berge グラフは確かに完璧グラフと同じであるという強い完璧グラフ定理を証明するために使用したときに重要になりました。Chudnovsky らは Chvátal の予想を直接証明することはできませんでしたが、代わりに、定理に対する最小の反例 (存在する場合) にはバランスのとれた歪分割 (端点が分割の片側にあり、内部頂点が反対側にあるすべての誘導パスの長さが均等である歪分割) は存在しないという弱い結果を証明しました。この結果は彼らの証明の重要な補題となり、Chvátal の補題の完全版は彼らの定理から導かれます。^[4]

歪分割は、Chudnovsky ら (2006) が強い完全グラフ定理の証明の一部として使用した完全グラフの構造分解の主要コンポーネントの 1 つです。Chudnovsky らは、すべての完全グラフが 5 つの基本完全グラフ クラスのいずれかに属しているか、またはより単純なグラフへの 4 種類の分解のいずれかを持ち、その 1 つが歪分割であることを示しました。

歪曲分割を使用した構造分解のより簡単な例は、Seymour (2006) によって示されています。彼は、すべての比較可能性グラフが完全、二部、または歪曲分割を持っていることを観察しています。なぜなら、半順序集合のすべての要素が最小要素または最大要素のいずれかである場合、対応する比較可能性グラフは二部です。順序が全順序である場合、対応する比較可能性グラフは完全です。これら 2 つのケースのどちらも発生しないが、最小でも最大でもないすべての要素が他のすべての要素と比較可能である場合、最小要素と非最小要素への分割 (最小要素が複数ある場合) または最大要素と非最大要素への分割 (最大要素が複数ある場合) のいずれかによって、スター カットセットが形成されます。残りのケースでは、部分順序の要素が存在し、その要素は最小でも最大でもなく、他のすべての要素と比較できません。この場合、相互に切断された側が（それ自体を含まない）比較可能な要素で構成され、切断された側が残りの要素で構成される歪んだ分割（スターカットセットの補集合）が存在します。 ${\displaystyle x}$${\displaystyle x}$${\displaystyle x}$

弦グラフには、同様のタイプのさらに単純な分解があります。つまり、完全であるか、クリーク セパレータがあるかのどちらかです。Hayward (1985) は、同様に、4 つ以上の頂点を持つ連結および共連結の弱弦グラフ (誘導サイクルまたはその補集合の長さが 4 より大きいグラフ) はすべて、スター カットセットまたはその補集合を持つことを示しました。このことから、Chvátal の補題により、そのようなグラフはすべて完全であることが示されます。

与えられたグラフの歪曲分割は、もし存在するなら、多項式時間で見つけられるかもしれない。これはもともと de Figueiredo ら (2000) によって示されたが、実行時間は と非現実的に長かった。ここで は入力グラフの頂点の数である。Kennedy & Reed (2008) は実行時間を に改善した。ここで は入力辺の数である。 ${\displaystyle O(n^{101})}$${\displaystyle n}$${\displaystyle O(n^{4}m)}$${\displaystyle m}$

グラフに、共切断側の部分の1つが独立している歪んだ分割が含まれているかどうかをテストすることはNP完全です。 ^[5] 与えられたグラフにバランスのとれた歪んだ分割が含まれているかどうかをテストすることも、任意のグラフではNP完全ですが、完全グラフでは多項式時間で解決できます。^[6]