團寬

圖論中，圖G的團寬（clique-width）是描述圖的結構複雜性的參數，與樹寬密切相關，但對稠密圖來說可以很小。團寬的定義是通過以下4種操作，構造G所需的最少標號數：

創建標籤為i的新頂點v，記作 $i(v)$ ；
兩有標圖G、H的不交並，記作 $G\oplus H$ ；
用邊連接標i的每個頂點與標j的每個頂點，記作 $\eta (i,\ j),\ i\neq j$ ；
將標籤i改為標籤j，記作 $\rho (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的葉在冪 $T^{k}$ 中的導出子圖。然而，指數無界的葉冪不具有有界團寬。^[7]

界編輯

Courcelle & Olariu (2000)、Corneil & Rotics (2005)證明，特定圖的團寬有下列邊界：

若圖的團寬不超過k，則所有導出子圖也不超過k。^[8]
k團寬圖的補圖的團寬不大於2k。^[9]
w樹寬圖的團寬不大於 $3\cdot 2^{w-1}$ 。此約束中的指數依賴是必須的：存在團寬比樹寬大指數級的圖。^[10]換一種說法，團寬有界圖可能有無界的樹寬，例如n頂點完全圖的團寬為2，而樹寬為 $n-1$ 。而沒有完全二分圖 $K_{t,\ t}$ 為子圖的k團寬圖，樹寬不大於 $3k(t-1)-1$ 。因此，所有稀疏圖族，樹寬有界等價於團寬有界。^[11]
秩寬的上下界都受團寬約束： ${\text{秩宽}}\leq {\text{团宽}}\leq 2^{{\text{秩宽}}+1}$ 。^[12]}}

另外，若圖G的團寬為k，則圖的次冪 $G^{c}$ 的團寬不大於 $2kc^{k}$ 。^[13]從樹寬得出的團寬約束與圖冪的團寬約束存在指數級差距，不過約束並不互相複合：若圖G的樹寬為w，則 $G^{c}$ 的團寬不大於 $2(c+1)^{w+1}-2$ ，只是樹寬的單指數級。^[14]

計算複雜度編輯

未解決的數學問題：能否在多項式時間內識別團寬有界圖？

很多對一般圖來說NP困難的優化問題，限定了團寬有界、已知圖的構造序列的條件後可用動態規劃高效解決。^[15]^[16]特別是，根據古賽爾定理的一種形式，可用MSO₁一元二階邏輯（允許量化頂點集的邏輯形式）表達的圖屬性，對團寬有界圖都有線性時間算法。^[16]

已知構造序列時，也有可能在多項式時間內為團寬有界圖找到最優圖著色或哈密頓環，但多項式的指數隨團寬增加，計算複雜度理論的證據表明這種依賴可能是必要的。^[17] 團寬有界圖是χ-有界的，這是說它們的色數最多是其最大團大小的函數。^[18]

運用基於裂分解的算法，可在多項式時間內識別出團寬為3的圖，並找到構造序列。^[19] 對團寬無界圖，精確計算團寬是NP困難的，獲得亞線性加性誤差的近似也是NP困難的。^[20]而團寬有界時，就可能在多項式時間內^[21]（特別是在頂點數的平方時間內^[22]）獲得寬度（比實際團寬大指數級）有界的構造序列。能否在固定參數可解時間內算得確切團寬或更優的近似值、能否在多項式時間內算得團寬的每個固定邊界、能否在多項式時間內識別團寬為4的圖，目前仍是未知的。^[20]

注釋編輯

^ 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 $\leq 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), MR 1431281.
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, doi:10.1016/S0166-218X(99)00184-5  .
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 $K n,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  .

[FOOTNOTECourcelleEngelfrietRozenberg1993-1] Courcelle, Engelfriet & Rozenberg (1993).

[FOOTNOTECourcelle1993-2] Courcelle (1993).

[FOOTNOTECourcelleOlariu2000-3] Courcelle & Olariu (2000).

[FOOTNOTEGolumbicRotics2000-4] Golumbic & Rotics (2000).

[FOOTNOTEBrandstädtLozin2003-5] Brandstädt & Lozin (2003).

[6] Brandstädt 等人 (2005); Brandstädt 等人 (2006).

[7] Brandstädt & Hundt (2008); Gurski & Wanke (2009).

[8] Courcelle & Olariu (2000), Corollary 3.3.

[9] Courcelle & Olariu (2000), Theorem 4.1.

[10] Corneil & Rotics (2005), strengthening Courcelle & Olariu (2000), Theorem 5.5.

[FOOTNOTEGurskiWanke2000-11] 11.0 ^11.1 Gurski & Wanke (2000).

[FOOTNOTEOumSeymour2006-12] Oum & Seymour (2006).

[FOOTNOTETodinca2003-13] Todinca (2003).

[FOOTNOTEGurskiWanke2009-14] Gurski & Wanke (2009).

[FOOTNOTECogisThierry2005-15] Cogis & Thierry (2005).

[FOOTNOTECourcelleMakowskyRotics2000-16] 16.0 ^16.1 Courcelle, Makowsky & Rotics (2000).

[FOOTNOTEFominGolovachLokshtanovSaurabh2010-17] Fomin et al. (2010).

[FOOTNOTEDvořákKrál'2012-18] Dvořák & Král' (2012).

[FOOTNOTECorneilHabibLanlignelReed2012-19] Corneil et al. (2012).

[FOOTNOTEFellowsRosamondRoticsSzeider2009-20] 20.0 ^20.1 Fellows et al. (2009).

[21] Oum & Seymour (2006); Hliněný & Oum (2008); Oum (2008); Fomin & Korhonen (2022).

[FOOTNOTEFominKorhonen2022-22] Fomin & Korhonen (2022).

[FOOTNOTEGurskiWanke2007-23] Gurski & Wanke (2007).

[FOOTNOTEBonnetKimThomasséWatrigant2022-24] Bonnet et al. (2022).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

團寬

目次

特殊圖類編輯

界編輯

計算複雜度編輯

相關寬參數編輯

注釋編輯

參考文獻編輯

團寬

特殊圖類 編輯

界 編輯

計算複雜度 編輯

相關寬參數 編輯

注釋 編輯

參考文獻 編輯

特殊圖類編輯

界編輯

計算複雜度編輯

相關寬參數編輯

注釋編輯

參考文獻編輯