Loading article…
グラフ理論では、グラフの族の浅いマイナーがすべてスパース グラフである場合、そのグラフの族は有界展開を持つと言われます。多くの自然なスパース グラフの族は有界展開を持ちます。密接に関連しているがより強い特性である 多項式展開は、これらの族の分離定理の存在と同等です。これらの特性を持つ族には、部分グラフ同型性問題やグラフの一次理論の モデル検査などの問題に対する効率的なアルゴリズムがあります。
定義と同等の特徴
グラフGのt浅いマイナーは、半径tの頂点が互いに素な部分グラフのコレクションを縮小し、 Gの残りの頂点を削除することによってGから形成されるグラフとして定義されます。グラフの族が有界展開を持つとは、族内のグラフのすべてのt浅いマイナーにおいて、辺と頂点の比が最大でf ( t ) になるような関数fが存在する場合です。[1]
有界展開のクラスの同等の定義は、すべての浅いマイナーがtの関数によって有界な彩色数を持つ、[1]または指定されたファミリが位相パラメータの有界値を持つ、である。このようなパラメータは、サブグラフを取ることに対して単調なグラフ不変量であり、パラメータ値はグラフが細分化されたときに制御された方法でのみ変化し、有界パラメータ値はグラフが有界退化を持つことを意味する。[2]
多項式展開と分離定理
より強い概念は多項式展開であり、これは浅いマイナーの辺密度を制限するために使用される関数fが多項式であることを意味します。遺伝グラフ族が、族内の任意のn頂点グラフは、定数c < 1 に対してO ( n c ) 頂点を除去することによって最大でn /2 頂点の断片に分割できるという分離定理に従う 場合、その族は必然的に多項式展開を持ちます。逆に、多項式展開を持つグラフには、部分線形分離定理があります。[3]
有界展開グラフのクラス
セパレータと展開の関係により、平面グラフの族を含むすべてのマイナー閉グラフ族は多項式展開を持つ。同じことが1 平面グラフにも当てはまり、より一般的には、辺あたりの交差数が制限された、種数が制限された曲面に埋め込むことができるグラフや、双クリークのない弦グラフにも当てはまる。これらはすべて、平面グラフと同様のセパレータ定理に従うからである。[4] [5] [6] [7]高次元ユークリッド空間では、空間の任意の点が制限された数のボールで覆われるという特性を持つボール系の交差グラフも、多項式展開を意味するセパレータ定理[8]に従う。
有界な本の厚さのグラフにはサブリニアセパレータはありませんが、[9]有界な展開もあります。[10]有界な展開の他のグラフには、有界次数のグラフ、 [11] エルデシュ・レーニイモデルにおける有界平均次数のランダムグラフ、[12]および有界キュー数のグラフがあります。[2] [13]
アルゴリズムアプリケーション
部分グラフ同型性問題のインスタンスでは、目標がサイズが制限されていない大きなグラフの部分グラフである、制限されたサイズのターゲットグラフを見つけることですが、大きなグラフが制限された拡張のグラフの族に属している場合は、線形時間で解決できます。同じことは、固定サイズのクリークを見つけること、固定サイズの支配セットを見つけること、またはより一般的には、グラフの第一階論理で制限されたサイズの式で表現できるプロパティをテストすることにも当てはまります。[14] [15]
多項式展開のグラフについては、集合被覆問題、最大独立集合問題、支配集合問題、その他いくつかの関連するグラフ最適化問題に対する多項式時間近似スキームが存在する。 [16]
参考文献
- ^ ab Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012)、「5.5 有界拡張を持つクラス」、Sparsity: Graphs, Structures, and Algorithms、Algorithms and Combinatorics、vol. 28、Springer、pp. 104–107、doi :10.1007/978-3-642-27875-4、ISBN 978-3-642-27874-7、MR 2920058。
- ^ ab Nešetřil, Jaroslav ; Ossona de Mendez, Patrice ; Wood, David R. (2012)、「境界付き展開によるグラフクラスの特徴と例」、European Journal of Combinatorics、33 (3): 350–373、arXiv : 0902.3265、doi :10.1016/j.ejc.2011.09.008、MR 2864421、S2CID 2633083。
- ^ Dvořák, Zdeněk; Norin, Sergey (2016)、「強準線形セパレータと多項式展開」、SIAM Journal on Discrete Mathematics、30 (2): 1095–1101、arXiv : 1504.04821、doi :10.1137/15M1017569、MR 3504982、S2CID 27395359
- ^ Nešetřil & Ossona de Mendez (2012)、14.2 Crossing Number、pp. 319–321。
- ^ Grigoriev, Alexander; Bodlaender, Hans L. (2007)、「辺あたりの交差が少ない埋め込み可能なグラフのアルゴリズム」、Algorithmica、49 (1): 1–11、doi :10.1007/s00453-007-0010-x、MR 2344391、S2CID 8174422。
- ^ Dujmović, Vida ; Eppstein, David ; Wood, David R. (2015)、「属、木幅、および局所交差数」、Proc. 23rd Int. Symp. Graph Drawing (GD 2015)、arXiv : 1506.04380、Bibcode :2015arXiv150604380D。
- ^ Fox, Jacob ; Pach, János (2009)、「文字列グラフのセパレータ定理とその応用」(PDF)、組合せ論、確率および計算、19 (3): 371、doi :10.1017/s0963548309990459、S2CID 5705145。
- ^ ミラー、ゲイリー L. ;テン、シャン・フア;サーストン、ウィリアム; ヴァヴァシス、スティーブン A. (1997)、「球パッキングと最近傍グラフのセパレータ」、Journal of the ACM、44 (1): 1–29、doi : 10.1145/256292.256294、MR 1438463。
- ^ ドゥイモヴィッチ、ヴィダ;シディロプロス、アナスタシオス。Wood、David R. (2015)、3-Monotone Expanders、arXiv : 1501.05020、Bibcode :2015arXiv150105020D
- ^ Nešetřil & Ossona de Mendez (2012)、14.5 スタック番号、327–328 ページ。
- ^ ネシェトジル & オッソナ・デ・メンデス (2012)、p. 307.
- ^ Nešetřil & Ossona de Mendez (2012)、14.1 ランダム グラフ (エルデシュ – レーニ モデル)、314 ～ 319 ページ。
- ^ Nešetřil & Ossona de Mendez (2012)、321–327 ページ。
- ^ Nešetřil & Ossona de Mendez (2012)、18.3 サブグラフ同型問題とブール クエリ、400–401 ページ。
- ^ Dvořák, Zdeněk ; Kráľ, Daniel ; Thomas, Robin (2010)、「スパースグラフの一次特性の決定」、Proc. 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010)、IEEE Computer Soc.、Los Alamitos、CA、pp. 133–142、MR 3024787。
- ^ Har-Peled, Sariel ; Quanrud, Kent (2015)、「多項式展開および低密度グラフの近似アルゴリズム」、Algorithms - ESA 2015、Lecture Notes in Computer Science、vol. 9294、Springer-Verlag、pp. 717–728、arXiv : 1501.00721、doi :10.1007/978-3-662-48350-3_60、ISBN 978-3-662-48349-7。