团宽
通过不交并、重标记与标签联接,构建团宽为3的距离遗传图 。顶点标签用颜色表示。
图论 中,图 G 的团宽 (clique-width)是描述图的结构复杂性的参数,与树宽 密切相关,但对稠密图 来说可以很小。
团宽的定义是通过以下4种操作,构造G 所需的最少标号 数:
创建标签为i 的新顶点v ,记作
i
(
v
)
{\displaystyle i(v)}
;
两有标图G 、H 的不交并 ,记作
G
⊕ ⊕ -->
H
{\displaystyle G\oplus H}
;
用边连接标i 的每个顶点与标j 的每个顶点,记作
η η -->
(
i
,
j
)
,
i
≠ ≠ -->
j
{\displaystyle \eta (i,\ j),\ i\neq j}
;
将标签i 改为标签j ,记作
ρ ρ -->
(
i
,
j
)
{\displaystyle \rho (i,\ j)}
团宽有界图包括余图 与距离遗传图 。在无界时计算团宽是NP困难 的,而有界时能否在多项式时间 内计算团宽也是未知的,不过已经有一些高效的团宽近似算法 。
基于这些算法与古赛尔定理 ,很多对任意图来说NP难的图优化问题都可在团宽有界图上快速求解或逼近。
Courcelle、Engelfriet、Rozenberg在1990年、Wanke (1994) 提出了作为团宽概念基础的构造序列。“团宽”一词始见于Chlebíková (1992) ,是用于另一个概念。1993年,这个词有了现在的含义。
特殊图类
余图 是团宽不大于2的图。距离遗传图 的团宽不大于3。单位区间图的团宽无界(基于网格结构)。
相似地,二分置换图团宽无界(基于相似的网格结构)。[ 5]
余图是没有任何导出子图与4顶点路径同构的图,根据这特征,对许多由禁导出子图定义的图类的团宽进行了分类。[ 6]
其他团宽有界图如k 值有界的k 叶幂 ,它们是树T 的叶在幂
T
k
{\displaystyle T^{k}}
中的导出子图 。然而,指数无界的叶幂不具有有界团宽。[ 7]
界
Courcelle & Olariu (2000) 、Corneil & Rotics (2005) 证明,特定图的团宽有下列边界:
若图的团宽不超过k ,则所有导出子图 也不超过k 。[ 8]
k 团宽图的补图 的团宽不大于2k 。[ 9]
w 树宽 图的团宽不大于
3
⋅ ⋅ -->
2
w
− − -->
1
{\displaystyle 3\cdot 2^{w-1}}
。此约束中的指数依赖是必须的:存在团宽比树宽大指数级的图。[ 10] 换一种说法,团宽有界图可能有无界的树宽,例如n 顶点完全图 的团宽为2,而树宽为
n
− − -->
1
{\displaystyle n-1}
。而没有完全二分图
K
t
,
t
{\displaystyle K_{t,\ t}}
为子图的k 团宽图,树宽不大于
3
k
(
t
− − -->
1
)
− − -->
1
{\displaystyle 3k(t-1)-1}
。因此,所有稀疏图 族,树宽有界等价于团宽有界。
秩宽 的上下界都受团宽约束:
秩宽
≤ ≤ -->
团宽
≤ ≤ -->
2
秩宽
+
1
{\displaystyle {\text{秩宽}}\leq {\text{团宽}}\leq 2^{{\text{秩宽}}+1}}
。}}
另外,若图G 的团宽为k ,则图的次幂
G
c
{\displaystyle G^{c}}
的团宽不大于
2
k
c
k
{\displaystyle 2kc^{k}}
。从树宽得出的团宽约束与图幂的团宽约束存在指数级差距,不过约束并不互相复合:
若图G 的树宽为w ,则
G
c
{\displaystyle G^{c}}
的团宽不大于
2
(
c
+
1
)
w
+
1
− − -->
2
{\displaystyle 2(c+1)^{w+1}-2}
,只是树宽的单指数级。
计算复杂度
很多对一般图来说NP困难 的优化问题,限定了团宽有界、已知图的构造序列的条件后可用动态规划 高效解决。特别是,根据古赛尔定理 的一种形式,可用MSO1 一元二阶逻辑 (允许量化顶点集的逻辑形式)表达的图属性 ,对团宽有界图都有线性时间算法。
已知构造序列时,也有可能在多项式时间内为团宽有界图找到最优图着色 或哈密顿环 ,但多项式的指数随团宽增加,计算复杂度理论的证据表明这种依赖可能是必要的。
团宽有界图是χ-有界 的,这是说它们的色数最多是其最大团大小的函数。
运用基于裂分解 的算法,可在多项式时间内识别出团宽为3的图,并找到构造序列。
对团宽无界图,精确计算团宽是NP困难 的,获得亚线性加性误差的近似也是NP困难的。而团宽有界时,就可能在多项式时间内[ 21] (特别是在顶点数的平方时间内)获得宽度(比实际团宽大指数级)有界的构造序列。能否在固定参数可解 时间内算得确切团宽或更优的近似值、能否在多项式时间内算得团宽的每个固定边界、能否在多项式时间内识别团宽为4的图,目前仍是未知的。
相关宽参数
有界团宽图理论类似于有界树宽 图,不同的是,团宽有界图可以稠密 。若图族的团宽有界,则要么其树宽也有界,要么每个完全二分图 都是图族中某个图的子图。树宽与团宽还通过线图 理论联系在一起:当且仅当图族的线图团宽都有界,图族的树宽有界。
团宽有界图的孪宽 (twin-width)也有界。
注释
参考文献
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), 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 [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 .