团宽

图论中，图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]

特殊图类

界

计算复杂度

相关宽参数

注释

参考文献