圖論中,無向圖割寬(cutwidth)是能滿足下列性質的最小整數k:圖存在頂點排序,使得將頂點劃分為排序的前後子集所得的至少跨過k條邊。具體點說,若將頂點編上號,則,使的邊最多有k條。[1]

割寬為2的圖。對所示的從左到右的頂點排序,每條垂線最多跨2條邊。

圖的割寬也叫做其耐折數(folding number)。[1]產生割寬的頂點排序以及計算這種排序與割寬的問題,統稱為最小割線性排列(minimum cut linear arrangement)。[2]

與其它參數的關係

編輯

割寬常常與圖的樹寬徑寬相等,不大於徑寬乘以 、樹寬乘以 ,其中 是最大度, 是頂點數。[3][4]若一族圖的最大度有界,且圖不含大小無界的完全二叉樹的細分,則族中的圖的割寬都有界。[4]次立方圖(subcubic graph,最大度為3的圖)中,割寬等於徑寬加一。[5]

割寬不小於任何圖的最小二等分數,即將頂點分為(儘可能)等大的兩子集時,橫跨兩側的邊數的最小值。圖的任意線性構圖(layout)在達到最佳割寬後,也能將構圖分為前後部,得到具有相同邊數的等分。割寬不大於最大度乘帶寬(bandwidth),即線性排列中分隔任意邊兩端點的最大步數。[6]相比於帶寬,將邊細分為多條邊的路徑後,割寬不變。它與「拓撲帶寬」有密切聯繫,即從給定圖的邊的細分能得到的最小帶寬。具體來說,對任何樹,其都在拓撲帶寬 與稍大的值 的區間內。[1]

刻寬(carving width)的定義與割寬類似,都指圖中跨越切口的邊數。然而,刻寬不像割寬那樣使用頂點的線性排序與割的線性序列,而是從頂點的分層聚類中導出的割,這使其與樹寬、枝寬更密切,而同徑寬、帶寬等不太相似。[7]

割寬可為交叉數提供一個下界,這是來自圖繪製(graph drawing)研究的概念。圖的交叉數是指:使頂點只連接自身為端點的邊,在平面上繪製圖時,相交邊對數的最小值。度有界的圖中,交叉數至少與割寬的平方成正比。對度無界的圖,更精確的下界是:[8] 其中,校正項與度的平方和成正比,是為解釋割寬平方與該量成正比,但交叉數為零的平面圖所必須的。[8]在另一種圖繪製——書嵌入(book embedding)中,定點被排列在一條線(「書脊」)上,邊則不交叉地排列在稱作「頁」(page)的半平面上,只在書脊處相交。書嵌入的頁寬(page width)是指在相同定點排序下,頁的最大割寬。[9]

計算複雜度

編輯

n個頂點的,可在 的時間內找到割寬,並構造出最佳寬度的線性構圖。[10]而對更一般的圖,是NP困難的;即使對度不大於3的平面圖,也是NP難的;即使輸入是樹,此問題的加權版本(最小化線性排列割邊的權)也是NP難的。[11]

割寬是最優線性排列問題之一,可通過赫爾德-卡普算法,運用動態規劃 時間內求解。[12]還有用量子演算法的更快算法,可在 時間內解決。[13]此外,這算法還是固定參數可解的:對任意定值 ,都可在線性時間內測出圖的割寬是否大於 ,若最大是c,則為其找到一個最優頂點排序。[2] 表示,運行此算法耗時 [14]另一種參數化算法適於少量頂點具有較高的度(使得割寬變大)的圖。若圖的頂點覆蓋大小有界,此算法可將問題轉化為變量更少、變量值受多項式約束的整數規劃。對樹寬有界的圖,由於「樹寬有界」包含割寬與頂點覆蓋數兩個參數,仍不知道此問題能否有效求解。[15]

稠密圖割寬有多項式時間近似算法[16]而對可能不稠密的圖,已知最佳近似率為 [17]這來自Tom Leighton與Satish Rao用遞歸二分法對定點排序,將近似割寬減小到最小二分數的方法,在近似率上損失了 的因子。[18]將這種遞歸二分法與Sanjeev Arora、Rao、烏梅什·瓦茲拉尼的最小二分數近似算法[19]結合起來,可得所述近似率。[17]小集合擴展假設下,不可能實現恆定的近似率。[17]

應用

編輯
通道布線問題,要在矩形區域內搭建出連接同編號管口的水平「通道」
使用5通道的解決方案

割寬的早期應用如超大規模集成電路設計中的通道布線問題,當中沿集成電路矩形區域的頂部、底部排列的元件的引腳必須通過導體連接起來。若元件可以從左到右自由排列,而元件引腳必須保持相連,那麼這就可以轉化為圖的線性排列的選擇問題,元件對應頂點,邊對應引腳間的導線。圖的割寬決定了電路布線所需通道數。[5]

蛋白質工程中,假設相關圖的割寬有界,可用於加速搜索編碼了蛋白質序列與二級結構mRNA序列。[20]

割寬問題的一個加權版本適用於有向無環圖,當中線性排序要與邊方向一致,這已用於計算任務序列的調度,調度方式可以最大限度地減少任務本身與維護通信數據所需的最大內存。[21]數據庫理論中,割寬問題的NP困難性被用於證明:執行連接時,為避免在磁盤與內存間反覆傳輸相同數據塊,同時在有限的內存中進行計算、安排這傳輸的問題,也是NP困難的。[22]

圖繪製中,割寬除了計算交叉數下界外,[8]還用於研究一種特殊的3維圖繪製,要求邊表示為最多1個折點的不交折線,頂點位於一條線上,頂點與折點必須有整數坐標。繪製這種圖,圖邊界框的最小體積必須至少與割寬乘頂點數成正比。頂點位於軸平行線上方時,總存在具有此體積的繪製。[23]

參考文獻

編輯
  1. ^ 1.0 1.1 1.2 Chung, Fan R. K. On the cutwidth and the topological bandwidth of a tree (PDF). SIAM Journal on Algebraic and Discrete Methods. 1985, 6 (2): 268–277 [2024-01-29]. MR 0778007. doi:10.1137/0606026. (原始內容存檔 (PDF)於2024-04-23). 
  2. ^ 2.0 2.1 Thilikos, Dimitrios M.; Serna, Maria; Bodlaender, Hans L. Cutwidth I: A linear time fixed parameter algorithm (PDF). Journal of Algorithms. 2005, 56 (1): 1–24 [2024-01-29]. MR 2146375. doi:10.1016/j.jalgor.2004.12.001. (原始內容存檔 (PDF)於2024-05-02). 
  3. ^ Korach, Ephraim; Solel, Nir. Tree-width, path-width, and cutwidth. Discrete Applied Mathematics. 1993, 43 (1): 97–101. MR 1218045. doi:10.1016/0166-218X(93)90171-J . 
  4. ^ 4.0 4.1 Chung, F. R. K.; Seymour, P. D. Graphs with small bandwidth and cutwidth (PDF). Discrete Mathematics. 1989, 75 (1-3): 113–119 [2024-01-29]. MR 1001391. doi:10.1016/0012-365X(89)90083-6. (原始內容存檔 (PDF)於2024-01-30). 
  5. ^ 5.0 5.1 Makedon, Fillia; Sudborough, Ivan Hal. On minimizing width in linear layouts. Discrete Applied Mathematics. 1989, 23 (3): 243–265. MR 0996137. doi:10.1016/0166-218X(89)90016-4 . 
  6. ^ Díaz, Josep; Petit, Jordi; Serna, Maria. A survey of graph layout problems (PDF). ACM Computing Surveys. September 2002, 34 (3): 313–356. doi:10.1145/568522.568523. 
  7. ^ Seymour, Paul D.; Thomas, Robin. Call routing and the ratcatcher. Combinatorica. 1994, 14 (2): 217–241. doi:10.1007/BF01215352. 
  8. ^ 8.0 8.1 8.2 Djidjev, Hristo N.; Vrt'o, Imrich. Crossing numbers and cutwidths. Journal of Graph Algorithms and Applications. 2003, 7 (3): 245–251. MR 2112230. doi:10.7155/jgaa.00069 . 
  9. ^ Stöhr, Elena. A trade-off between page number and page width of book embeddings of graphs. Information and Computation. 1988, 79 (2): 155–162. MR 0968104. doi:10.1016/0890-5401(88)90036-3 . 
  10. ^ Yannakakis, Mihalis. A polynomial algorithm for the min-cut linear arrangement of trees. Journal of the ACM. 1985, 32 (4): 950–988. MR 0810346. doi:10.1145/4221.4228 . 
  11. ^ Monien, B.; Sudborough, I. H. Min cut is NP-complete for edge weighted trees. Theoretical Computer Science. 1988, 58 (1-3): 209–229. MR 0963264. doi:10.1016/0304-3975(88)90028-X . 
  12. ^ Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M. A note on exact algorithms for vertex ordering problems on graphs. Theory of Computing Systems. 2012, 50 (3): 420–432. MR 2885638. S2CID 9967521. doi:10.1007/s00224-011-9312-0. hdl:1956/4556 . 
  13. ^ Ambainis, Andris; Balodis, Kaspars; Iraids, Jānis; Kokainis, Martins; Prūsis, Krišjānis; Vihrovs, Jevgēnijs. 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: 1783–1793. 2019. MR 3909576. arXiv:1807.05209 . doi:10.1137/1.9781611975482.107. 
  14. ^ Giannopoulou, Archontia C.; Pilipczuk, Jean-Florent, Michałand Raymond; Thilikos, Dimitrios M.; Wrochna, Marcin. Cutwidth: obstructions and algorithmic aspects (PDF). Algorithmica. 2019, 81 (2): 557–588 [2024-01-29]. MR 3910081. doi:10.1007/s00453-018-0424-7. (原始內容存檔 (PDF)於2024-01-30). 
  15. ^ Fellows, Michael R.; Lokshtanov, Daniel; Misra, Neeldhara; Rosamond, Frances A.; Saurabh, Saket. Hong, Seok-Hee; Nagamochi, Hiroshi; Fukunaga, Takuro , 編. Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15–17, 2008, Proceedings. Lecture Notes in Computer Science 5369. Springer: 294–305. 2008. doi:10.1007/978-3-540-92182-0_28. 
  16. ^ Arora, Sanjeev; Frieze, Alan; Kaplan, Haim. A new rounding procedure for the assignment problem with applications to dense graph arrangement problems. Mathematical Programming. 2002, 92 (1, Ser. A): 1–36 [2024-01-29]. MR 1892295. doi:10.1007/s101070100271. (原始內容存檔於2023-04-09). 
  17. ^ 17.0 17.1 17.2 Wu, Yu; Austrin, Per; Pitassi, Toniann; Liu, David. Inapproximability of treewidth, one-shot pebbling, and related layout problems. Journal of Artificial Intelligence Research. 2014, 49: 569–600. MR 3195329. doi:10.1613/jair.4030 . 
  18. ^ Leighton, Tom; Rao, Satish. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM. 1999, 46 (6): 787–832. MR 1753034. doi:10.1145/331524.331526 . 
  19. ^ Arora, Sanjeev; Rao, Satish; Vazirani, Umesh. Expander flows, geometric embeddings and graph partitioning (PDF). Journal of the ACM. 2009, 56 (2): Art. 5, 37 [2024-01-29]. MR 2535878. doi:10.1145/1502793.1502794. (原始內容存檔 (PDF)於2024-06-16). 
  20. ^ Blin, Guillaume; Fertin, Guillaume; Hermelin, Danny; Vialette, Stéphane. Fixed-parameter algorithms for protein similarity search under mRNA structure constraints. Journal of Discrete Algorithms. 2008, 6 (4): 618–626. MR 2463425. doi:10.1016/j.jda.2008.03.004 . 
  21. ^ Kayaaslan, Enver; Lambert, Thomas; Marchal, Loris; Uçar, Bora. Scheduling series-parallel task graphs to minimize peak memory. Theoretical Computer Science. 2018, 707: 1–23. MR 3734396. doi:10.1016/j.tcs.2017.09.037 . 
  22. ^ Fotouhi, Farshad; Pramanik, Sakti. Problem of optimizing the number of block accesses in performing relational join is NP-hard. Information Processing Letters. 1991, 38 (5): 271–275. MR 1114421. doi:10.1016/0020-0190(91)90070-X. 
  23. ^ Morin, Pat; Wood, David R. Three-dimensional 1-bend graph drawings. Journal of Graph Algorithms and Applications. 2004, 8 (3): 357–366. MR 2176967. doi:10.7155/jgaa.00095 .