奇数サイクル横断

グラフ理論において、無向グラフの奇数サイクル横断とは、グラフ内のすべての奇数サイクルと空でない交差を持つグラフの頂点の集合である。グラフから奇数サイクル横断の頂点を除去すると、残りの誘導部分グラフとして二部グラフが残る。^[1]

与えられた-頂点グラフがサイズ の奇数サイクル横断を持つ場合と、グラフの直積( の 2 つのコピーで構成され、各コピーの対応する頂点が完全マッチングの辺で接続されたグラフ) がサイズ の頂点カバーを持つ場合とで同じです。奇数サイクル横断は、横断からの各頂点の両方のコピーと、残りの各頂点の 1 つのコピー (2 つのコピーから、その頂点が二分割のどちら側に含まれるかに応じて選択) を含めることで、頂点カバーに変換できます。反対に、 の頂点カバーは、両方のコピーがカバーに含まれる頂点のみを保持することで、奇数サイクル横断に変換できます。結果として得られる横断の外側の頂点は、カバーで使用された頂点のコピーに応じて二分割できます。^[1]${\displaystyle n}$${\displaystyle G}$${\displaystyle k}$ ${\displaystyle G\square K_{2}}$${\displaystyle G}$${\displaystyle n+k}$${\displaystyle G\square K_{2}}$

最小の奇数サイクル横断、または同等に最大の二部誘導部分グラフを見つける問題は、奇数サイクル横断とも呼ばれ、OCTと略される。これは、遺伝的性質を持つ最大の誘導部分グラフを見つける問題の特別なケースとしてNP困難である（二部であるという性質は遺伝的である）。このような非自明な性質の問題はすべてNP困難である。^{[2] [3]}

奇数サイクル横断問題と頂点被覆問題との同等性は、奇数サイクル横断に対する固定パラメータで扱いやすいアルゴリズムの開発に利用されてきた。つまり、実行時間がグラフのサイズの多項式関数に のより大きな関数を乗じたもので制限されるアルゴリズムが存在するということである。これらのアルゴリズムの開発は、他の多くのパラメータ化アルゴリズムのためのより一般的なツールである反復圧縮法につながった。 ^[1]これらの問題に対して知られているパラメータ化アルゴリズムは、 の任意の固定値に対してほぼ線形時間を要する。^[4]あるいは、グラフのサイズに多項式依存性がある場合、 への依存性はまで小さくすることができる。^{[5]対照的に、}有向グラフ に対する類似の問題は、標準的な複雑性理論の仮定の下では固定パラメータで扱いやすいアルゴリズムを許容しない。^[6]${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle 2.3146^{k}}$

• 最大カット、つまり、削除すると二部グラフになるような辺の最小集合を求めることと同等である。