カット幅
グラフ理論における性質
カット幅 2 のグラフ。示されているように、頂点は左から右に順序付けられており、各垂直線は最大 2 つのエッジと交差します。

グラフ理論において、無向グラフのカット幅は、グラフの頂点に順序があり、その順序の前後のサブセットに頂点を分割することで得られるすべてのカットは、最大で本の辺によって交差されるという性質を持つ最小の整数である。つまり、頂点に という番号が付けられている場合、任意の に対して、とを持つ辺の数は最大で である。[1] け {\displaystyle k} け {\displaystyle k} v 1 、 v 2 、 … v n {\displaystyle v_{1},v_{2},\dots v_{n}} ℓ ＝ 1 、 2 、 … n − 1 {\displaystyle \ell =1,2,\dots n-1} v 私 v j {\displaystyle v_{i}v_{j}} 私 ≤ ℓ {\displaystyle i\leq \ell } j > ℓ {\displaystyle j>\ell } け {\displaystyle k}

グラフのカット幅は折り畳み数とも呼ばれる。[1]カット幅を生成する頂点順序と、この順序とカット幅を計算する問題は、最小カット線形配置と呼ばれている。[2]

他のパラメータとの関係

カット幅は、グラフの他のいくつかの幅パラメータと関連しています。特に、カット幅は常に同じグラフのツリー幅またはパス幅と少なくとも同じ大きさです。ただし、最大でパス幅の 倍、またはツリー幅の 倍になります。ここで、 は最大次数、は頂点数です。[3] [4]グラフ族の最大次数が制限されており、そのグラフに無制限のサイズを持つ完全二分木の細分が含まれていない場合、その族のグラフのカット幅は制限されています。[4]サブキュービックグラフ（最大次数が3のグラフ）では、カット幅はパス幅に1を加えた値になります。[5] お （ Δ ） {\displaystyle O(\Delta )} O ( Δ log ⁡ n ) {\displaystyle O(\Delta \log n)} Δ {\displaystyle \Delta } n {\displaystyle n}

カット幅は、任意のグラフの最小二分数以上である。これは、頂点を等しいサイズ（または可能な限り等しいサイズに近い）の2つの部分集合に分割する際に、一方の辺から他方の辺への辺の最小数である。グラフの線形レイアウトは、最適なカット幅を達成すると、レイアウトを前半と後半に分割することで得られる、同じ辺数の二分も得られる。カット幅は、グラフの帯域幅（この量を最小化するように選択された線形配置において、任意の辺の端点間の最大ステップ数）に最大次数を乗じた値以下である。[6]帯域幅とは異なり、カット幅は、辺が複数の辺のパスに細分化されても変化しない。これは、「位相帯域幅」、つまり与えられたグラフの辺を細分化することで得られる最小帯域幅と密接に関連している。特に、任意の木の場合、カット幅は位相帯域幅とわずかに大きい数の間に挟まれている。[1] b ∗ {\displaystyle b^{*}} b ∗ + log 2 ⁡ b ∗ + 2 {\displaystyle b^{*}+\log _{2}b^{*}+2}

グラフ内のカットをまたぐ辺の数という点でカット幅と同様に定義されるもう1つのパラメータは、カービング幅です。しかし、カット幅のように頂点の線形順序とカットの線形シーケンスを使用するのではなく、カービング幅は頂点の階層的クラスタリングから得られるカットを使用するため、ツリー幅やブランチ幅との関連性が高く、パス幅や帯域幅などの線形順序を含む他の幅パラメータとの関連性は低くなります。[7]

カット幅は、グラフ描画の研究で生じる別のパラメータである交差数の下限値を提供するために使用できます。グラフの交差数とは、各頂点がそれを端点とする辺とのみ接する平面上のグラフの任意の描画において、交差する辺のペアの最小数です。次数が制限されているグラフでは、交差数は常にカット幅の 2 乗に少なくとも比例します。次数が制限されていないグラフに適用されるより正確な上限は次のとおりです。[8] ここで、次数の 2 乗の合計に比例する補正項は、カット幅の 2 乗がこの量に比例するが交差数が 0 である平面グラフの存在を説明するために必要です。 [8]別のスタイルのグラフ描画であるブック埋め込みでは、頂点は直線上に配置され、辺はこの直線で交わる別々の半平面ページに交差することなく配置されます。本の埋め込みのページ幅は、同じ頂点順序を使用して、ページの最大のカット幅として定義されています。[9] crossings ⁡ ( G ) ≥ 1 1176 cutwidth ⁡ ( G ) 2 − ∑ v ∈ V ( G ) ( deg ⁡ ( v ) 4 ) 2 . {\displaystyle \operatorname {crossings} (G)\geq {\frac {1}{1176}}\operatorname {cutwidth} (G)^{2}-\sum _{v\in V(G)}\left({\frac {\deg(v)}{4}}\right)^{2}.}

計算の複雑さ

頂点のツリーに対しては、カット幅を求め、最適な幅の線形レイアウトを時間内に構築することができる。[10]より一般的なグラフに対しては、これはNP困難である。最大次数3の平面グラフであってもNP困難であり、問​​題の重み付きバージョン（線形配置の任意のカットを通る辺の重みを最小化する問題）は、入力がツリーであってもNP困難である。[11] O ( n log ⁡ n ) {\displaystyle O(n\log n)} n {\displaystyle n}

カット幅は、最適線形配置の多くの問題のうちの 1 つで、動的計画法を用いたHeld-Karp アルゴリズムによって時間 で正確に解くことができます。[12]時間 を伴う、より高速な量子アルゴリズムも知られています。[13]さらに、これは固定パラメータで扱いやすいです。 の任意の固定値に対して、グラフのカット幅が最大で であるかどうかをテストし、そうである場合は線形時間でグラフの最適な頂点順序付けを見つけることができます。[2]より正確には、との両方について、このアルゴリズムの実行時間は です。[14]少数の頂点が高次である (カット幅が大きくなる) グラフに適した別のパラメータ化アルゴリズムでは、代わりに、グラフの頂点被覆のサイズが制限されている場合、変数が少なく変数値に多項式境界がある整数計画問題に変換することで、の多項式時間で問題を解きます。木幅が制限されたグラフに対してこの問題を効率的に解くことができるかどうかは未解決のままである。木幅が制限されたグラフでは、カット幅と頂点被覆数の両方によるパラメータ化が包含されることになる。[15] O ( n 2 n ) {\displaystyle O(n2^{n})} O ( 1.817 n ) {\displaystyle O(1.817^{n})} c {\displaystyle c} c {\displaystyle c} n {\displaystyle n} c {\displaystyle c} 2 O ( c 2 ) n {\textstyle 2^{O(c^{2})}n} n {\displaystyle n}

Cutwidth には、稠密なグラフに対する多項式時間近似スキームがあります[ 16 ]が、稠密でない可能性のあるグラフの場合、知られている最良の近似比はです。[17]これは、頂点の順序付けに再帰二分法を使用することで近似比の係数 を失うことで、近似カット幅を最小二分数に減らすTom LeightonとSatish Raoの方法に由来します。 [18]この再帰二分法を、最小二分数を近似するSanjeev Arora、Rao、およびUmesh Vaziraniの別の方法[19]と組み合わせると、指定された近似比が得られます。[17]小集合展開仮説の下では、定数近似比を実現することは不可能です。[17] O ( ( log ⁡ n ) 3 / 2 ) {\textstyle O{\bigl (}(\log n)^{3/2}{\bigr )}} log 2 ⁡ n {\displaystyle \log _{2}n}

アプリケーション

カット幅の初期の応用例としては、VLSI設計におけるチャネル配線が挙げられます。この配線では、集積回路の長方形領域の上部と下部に配置されたコンポーネントは、コンポーネントに接続されたピンのペアを接続する導体によって接続されます。コンポーネントを左から右への順序に自由に配置できる一方で、各コンポーネントのピンは連続している必要がある場合、これは各コンポーネントを頂点とし、各ピン間の接続を辺とするグラフの線形配置を選択する問題に置き換えることができます。グラフのカット幅は、回路を配線するために必要なチャネル数を制御します。[5]

タンパク質工学では、関連グラフが制限されたカット幅を持つという仮定が、与えられたタンパク質配列をコードし、同時に与えられた二次構造に折り畳まれるmRNA配列の探索を高速化するために使用されてきた。[20]

有向非巡回グラフに適用され、グラフのエッジの向きと一致する線形順序付けのみを許可する問題の重み付き変種は、タスク自体とタスク間通信に使用されるデータの両方について、スケジュールに必要なメモリの最大量を最小化する方法で計算タスクのシーケンスをスケジュールするために適用されています。[21]データベース理論では、カット幅問題のNP困難性を使用して、結合を実行するときにディスクとメインメモリの間でデータブロックの転送をスケジュールすることもNP困難であることを示しています。これにより、限られた量のメインメモリ内で計算を収めながら、同じブロックの繰り返し転送を回避できます。[22]

グラフ描画において、カット幅は交差数の下限値に適用されるだけでなく、[8]特定の種類の3次元グラフ描画の研究にも適用されている。このグラフ描画では、エッジは最大1つの屈曲部を持つ互いに素な多角形鎖として表現され、頂点は直線上に配置され、すべての頂点と屈曲点は整数座標を持つ必要がある。この種の描画では、描画の境界ボックスの最小体積は、少なくともカット幅と頂点数の積に比例する必要がある。この体積を持つ描画は常に存在し、頂点は軸に平行な直線上に配置されます。[23]

参考文献

  1. ^ abc Chung, Fan RK (1985). 「木のカット幅と位相帯域幅について」(PDF) . SIAM Journal on Algebraic and Discrete Methods . 6 (2): 268– 277. doi :10.1137/0606026. MR  0778007.
  2. ^ ab ティリコス、ディミトリオス M.;マリア・セルナ;ハンス L. ボドレンダー(2005)。 「カット幅 I: 線形時間固定パラメーター アルゴリズム」(PDF)。アルゴリズムのジャーナル。56 (1): 1–24 .土井:10.1016/j.jalgor.2004.12.001。MR  2146375。
  3. ^ コラク、エフライム；ソレル、ニル（1993）「ツリー幅、パス幅、カット幅」離散応用数学. 43 (1): 97– 101. doi : 10.1016/0166-218X(93)90171-J . MR  1218045.
  4. ^ ab Chung, FRK ; Seymour, PD (1989). 「小さな帯域幅とカット幅を持つグラフ」(PDF) .離散数学. 75 ( 1–3 ): 113– 119. doi :10.1016/0012-365X(89)90083-6. MR  1001391.
  5. ^ ab Makedon, Fillia ; Sudborough, Ivan Hal (1989). 「線形レイアウトにおける幅の最小化について」.離散応用数学. 23 (3): 243– 265. doi : 10.1016/0166-218X(89)90016-4 . MR  0996137.
  6. ^ Díaz, Josep; Petit, Jordi; Serna, Maria (2002年9月). 「グラフレイアウト問題に関するサーベイ」(PDF) . ACM Computing Surveys . 34 (3): 313– 356. doi :10.1145/568522.568523.
  7. ^ Seymour, Paul D. ; Thomas, Robin (1994). 「コールルーティングとラットキャッチャー」. Combinatorica . 14 (2): 217– 241. doi :10.1007/BF01215352.
  8. ^ abc Djidjev, Hristo N.; Vrt'o, Imrich (2003). 「交差数とカット幅」. Journal of Graph Algorithms and Applications . 7 (3): 245– 251. doi : 10.7155/jgaa.00069 . MR  2112230.
  9. ^ Stöhr, Elena (1988). 「グラフの埋め込みにおけるページ数とページ幅のトレードオフ」. Information and Computation . 79 (2): 155– 162. doi : 10.1016/0890-5401(88)90036-3 . MR  0968104.
  10. ^ Yannakakis, Mihalis (1985). 「木の最小カット線形配置のための多項式アルゴリズム」. Journal of the ACM . 32 (4): 950–988 . doi : 10.1145/4221.4228 . MR  0810346.
  11. ^ Monien, B.; Sudborough, IH (1988). 「最小カットは辺重み付き木に対してNP完全である」.理論計算機科学. 58 ( 1–3 ): 209–229 . doi : 10.1016/0304-3975(88)90028-X . MR  0963264.
  12. ^ Bodlaender, Hans L. ; Fomin, Fedor V. ; Koster, Arie MCA ; Kratsch, Dieter ; Thilikos, Dimitrios M. (2012). 「グラフ上の頂点順序付け問題に対する正確なアルゴリズムに関するノート」.計算システム理論. 50 (3): 420– 432. doi :10.1007/s00224-011-9312-0. hdl : 1956/4556 . MR  2885638. S2CID  9967521.
  13. ^ Ambainis, Andris; Balodis, Kaspars; Iraids, Jānis; Kokainis, Martins; Prūsis, Krišjānis; Vihrovs, Jevgēnijs (2019). 「指数時間動的計画アルゴリズムの量子高速化」. Chan, Timothy M. (編). Proceedings of the Thirtieth Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6–9, 2019 . Society for Industrial and Applied Mathematics. pp.  1783– 1793. arXiv : 1807.05209 . doi :10.1137/1.9781611975482.107. MR  3909576。
  14. ^ ジャンノプルー、Archontia C.;ピリップチュク、ジャン＝フロラン、ミハランド・レイモンド。ティリコス、ディミトリオス M.マルシン、ウォシュナ (2019)。 「カット幅: 障害物とアルゴリズムの側面」(PDF)。アルゴリズム。81 (2): 557–588。土井:10.1007/s00453-018-0424-7。MR  3910081。{{cite journal}}: CS1 maint: multiple names: authors list (link)
  15. ^ Fellows, Michael R. ; Lokshtanov, Daniel; Misra, Neeldhara; Rosamond, Frances A. ; Saurabh, Saket (2008). 「頂点被覆率によってパラメータ化されたグラフレイアウト問題」(PDF) . Hong, Seok-Hee ; Nagamochi, Hiroshi ; Fukunaga, Takuro (eds.). Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15–17, 2008, Proceedings . Lecture Notes in Computer Science. Vol. 5369. Springer. pp.  294– 305. doi :10.1007/978-3-540-92182-0_28.
  16. ^ Arora, Sanjeev ; Frieze, Alan ; Kaplan, Haim (2002). 「割り当て問題のための新しい丸め手順と稠密グラフ配置問題への応用」.数学プログラミング. 92 (1, Ser. A): 1– 36. doi :10.1007/s101070100271. MR  1892295.
  17. ^ abc Wu, Yu; Austrin, Per; Pitassi, Toniann ; Liu, David (2014). 「ツリー幅の近似不可能性、ワンショットペブリング、および関連するレイアウト問題」. Journal of Artificial Intelligence Research . 49 : 569–600 . doi : 10.1613/jair.4030 . MR  3195329.
  18. ^ レイトン, トム;ラオ, サティッシュ(1999). 「マルチコモディティ最大フロー最小カット定理と近似アルゴリズムの設計におけるその利用」. Journal of the ACM . 46 (6): 787– 832. doi : 10.1145/331524.331526 . MR  1753034.
  19. ^ Arora, Sanjeev ; Rao, Satish ; Vazirani, Umesh (2009). 「Expander flows, geometric embeddings and graph partitioning」（PDF） . Journal of the ACM . 56 (2): Art. 5, 37. doi :10.1145/1502793.1502794. MR  2535878.
  20. ^ Blin, Guillaume; Fertin, Guillaume; Hermelin, Danny; Vialette, Stéphane (2008). 「mRNA構造制約下でのタンパク質類似性検索のための固定パラメータアルゴリズム」. Journal of Discrete Algorithms . 6 (4): 618– 626. doi : 10.1016/j.jda.2008.03.004 . MR  2463425.
  21. ^ Kayaaslan, Enver; Lambert, Thomas; Marchal, Loris; Uçar, Bora (2018). 「ピークメモリを最小化するための直並列タスクグラフのスケジューリング」.理論計算機科学. 707 : 1– 23. doi : 10.1016/j.tcs.2017.09.037 . MR  3734396.
  22. ^ Fotouhi, Farshad; Pramanik, Sakti (1991). 「リレーショナル結合におけるブロックアクセス回数の最適化問題はNP困難である」. Information Processing Letters . 38 (5): 271– 275. doi :10.1016/0020-0190(91)90070-X. MR  1114421.
  23. ^ Morin, Pat ; Wood, David R. (2004). 「3次元1ベンドグラフ描画」. Journal of Graph Algorithms and Applications . 8 (3): 357– 366. doi : 10.7155/jgaa.00095 . MR  2176967.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Cutwidth&oldid=1329655861"