浅いマイナー

グラフ理論において、浅いマイナーまたは深さが制限されたマイナーは、グラフマイナーの制限された形式であり、マイナーを形成するために縮約されるサブグラフの直径は小さい。浅いマイナーは、Plotkin、Rao、Smith (1994) によって導入され、彼らはその発明をCharles E. Leisersonと Sivan Toledo に帰した。^[1]

無向グラフGのマイナーを定義する方法の 1 つは、 GのサブグラフHと、それぞれがHの連結された誘導サブグラフH _iを形成する、 Gの頂点の互いに素なサブセットS _iのコレクションを指定することです。マイナーには、各サブセットS _iごとに頂点v _{i が}あり、 Hに属するS _iからS _jへの辺が存在する場合は常に辺 v _i v _{j が}あります。

この定式化では、d浅いマイナー（深さdの浅いマイナーとも呼ばれる）は、各サブグラフH _iの半径が最大でもdになるように定義できるマイナーであり、つまり、H _iの他のすべての頂点から距離d以内にある中心頂点c _{i を}含む。この距離はH _iのホップ数によって測定されるため、 Gの距離よりも大きくなる可能性があることに注意してください。^[1]

深さ 0 の浅いマイナーは、与えられたグラフのサブグラフと同じものです。d の値が十分に大きい場合(頂点の数と同じかそれ以上の値を含む)、与えられたグラフのd浅いマイナーは、そのすべてのマイナーと一致します。^[1]

Nešetřil & Ossona de Mendez (2012) は、浅いマイナーを使用して有限グラフの族を 2 つのタイプに分割します。彼らは、グラフ族Fがどこか稠密であるとは、 dの有限値が存在し、その値に対してF内のグラフのd浅いマイナーがすべての有限グラフで構成される場合をいいます。そうでない場合、グラフ族はどこにも稠密ではないと言います。^[2]この用語は、F がどこにも稠密ではないグラフのクラスである場合、(すべての ε > 0 について) F内のn頂点グラフにはO ( n ^{1 + ε} ) の辺があるため、どこにも稠密ではないグラフは疎なグラフであるという事実によって正当化されます。^[3]

同様に説明される、より制限的なタイプのグラフ族は、有界展開のグラフ族である。これらは、あらゆるd浅いマイナーにおける辺と頂点の比が最大でf ( d ) となるような関数f が存在するグラフ族である。^{[4]この関数が存在し、}多項式によって有界となる場合、グラフ族は多項式展開を持つと言われる。

Plotkin、Rao & Smith (1994) が示したように、排除された浅いマイナーを持つグラフは、平面グラフの平面セパレータ定理と同様に分割できます。特に、完全グラフK _hがn頂点グラフGのd浅いマイナーでない場合、サイズがO ( dh ² log n + n / d ) であるGのサブセットS が存在し、G \ Sの各接続コンポーネントは最大で 2 n /3 個の頂点を持ちます。結果は構成的です。つまり、そのようなセパレータ、またはd浅いK _hマイナーを見つける多項式時間アルゴリズムが存在します。 ^[5] 結果として、彼らは、マイナーが閉じたグラフファミリはすべて、平面グラフのセパレータ定理とほぼ同じくらい強いセパレータ定理に従うことを示し

Plotkin らは、この結果を高次元の有限要素法メッシュの分割にも適用しました。この一般化には、浅いマイナーが必要です。これは、(深さの制限がない場合) 3 次元以上のメッシュ ファミリには、すべてのグラフがマイナーとして含まれるためです。Teng (1998) は、これらの結果をより広範な高次元グラフのクラスに拡張しました。

より一般的には、遺伝的グラフ族にはセパレータ定理があり、セパレータのサイズはnの線形以下のべき乗であり、多項式展開を持つ場合に限ります。^[6]

• ドヴォルザーク, ズデニク; Norin、Sergey (2015)、強力にサブリニアなセパレーターと多項式展開、arXiv : 1504.04821、Bibcode :2015arXiv150404821D。
• Plotkin, Serge; Rao, Satish; Smith, Warren D. (1994)、「浅い除外マイナーと改良されたグラフ分解」、Proc. 5th ACM-SIAM Symp. on Discrete Algorithms (SODA)、pp. 462–470。
• Teng, Shang-Hua (1998)、「幾何学的グラフの組み合わせ的側面」、Comput. Geom.、9 (4): 277–287、doi : 10.1016/S0925-7721(96)00008-9、MR  1609578。
• Wulff-Nilsen, Christian (2011)、「マイナーフリーおよび浅いマイナーフリーグラフのセパレータ定理とその応用」、Proc. 52nd IEEE Symp. Foundations of Computer Science (FOCS)、pp. 37–46、arXiv : 1107.1292、doi :10.1109/FOCS.2011.15、ISBN 978-0-7695-4571-4。
• Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012)、Sparsity: Graphs, Structures, and Algorithms、Algorithms and Combinatorics、vol. 28、Springer、doi :10.1007/978-3-642-27875-4、ISBN 978-3-642-27874-7、MR  2920058。