誘導マッチング

グラフ理論において、誘導マッチングまたは強マッチングとは、無向グラフの辺のサブセットであり、頂点を共有しないもの（マッチングである）であり、マッチング辺の端点である任意の2つの頂点を結ぶ唯一の辺である（誘導サブグラフである）。

誘導マッチングは、与えられたグラフの線グラフの正方形内の独立集合として記述することもできます。^{[ 1 ]}

グラフのエッジが誘導されるマッチングの最小数${\displaystyle G}$分割できるものは、その強い彩色指数と呼ばれ、${\displaystyle \chi _{s}'(G)}$色指数との類推により${\displaystyle \chi '(G)}$グラフの、その辺を分割できる最小マッチング数。^{[ 2 ]}これは線グラフの二乗の彩色数に等しい。 線グラフの二乗に適用されるブルックスの定理は、強い彩色指数が与えられたグラフの最大次数に対してせいぜい2乗であることを示しているが、2乗の上限のより良い定数係数は他の方法で得ることができる。^{[ 3 ]}

Ruzsa –Szemerédi 問題は、線形強彩色指数を持つ平衡二部グラフのエッジ密度に関するものです。同様に、これは、すべての頂点の近傍が誘導マッチングである局所的に線形なグラフという、別のクラスのグラフの密度に関するものです。 ^{[ 4 ]}これらのタイプのグラフはどちらもエッジ数が2乗になることはありませんが、エッジ数がほぼ2乗になるタイプのグラフの構成法は知られています。^{[ 5 ]}

少なくともサイズの誘導マッチングを見つける${\displaystyle k}$はNP完全問題であり（したがって、最大サイズの誘導マッチングを見つけることはNP困難である）、弦グラフでは多項式時間で解くことができる。これは、弦グラフの線グラフの二乗が完全グラフであるためである。^{[ 6 ]}さらに、弦グラフ では線形時間で解くことができる。 ^{[ 7 ]}多項式階層に予期せぬ崩壊が発生しない限り、最大の誘導マッチングは、いかなる精度でも近似することはできない。${\displaystyle n^{1-\varepsilon }}$多項式時間での近似比。 ^{[ 8 ]}

この問題はW[1]困難でもあり、与えられたサイズの小さな誘導マッチングを見つけることさえ困難である。${\displaystyle k}$総当たり探索アプローチよりも大幅に高速なアルゴリズムは存在しない可能性が高い。${\displaystyle k}$-エッジのタプル。^{[ 9 ]}しかし、見つける問題は${\displaystyle k}$除去すると誘導マッチングが残る頂点は固定パラメータで扱いやすい。^{[ 10 ]}この問題は、${\displaystyle n}$-時間軸上の頂点グラフ${\displaystyle O(1.3752^{n})}$指数関数的な空間、あるいは時間において${\displaystyle O(1.4231^{n})}$多項式空間を持つ。^{[ 11 ]}

• 誘導経路