클라이크 폭
Clique-width
그래프 이론에서 그래프 의 clique-width는 그래프의 구조적 복잡성을 설명하는 매개변수로, 나무 폭과 밀도가 높은 그래프에 대해서도 경계를 지정할 수 있다.이 값은 다음 4개의 연산을 통해 을(를) 구성하는 데 필요한 최소 라벨 수로 정의된다.
- 라벨 i를 사용하여 새 꼭지점 v 생성(표시 i(v) )
- 레이블이 지정된 두 그래프 G와 H의 결합 해제(g H로 표시됨)
- 가장자리로 결합하는 모든 정점(i,j로 표시됨), 여기서 verte j {\ j
- j 레이블로 레이블 i 이름 바꾸기( ((i,j)로 표시됨)
경계된 클라이크 폭의 그래프에는 cograph와 거리-계통 그래프가 포함된다.한이 없을 때 클라이크 너비를 계산하는 것은 NP-힘이고, 경계가 되는 다항 시간에 계산할 수 있는지는 알 수 없지만, 클라이크 너비에 대한 효율적인 근사 알고리즘은 알려져 있다.이러한 알고리즘과 쿠르셀의 정리에 기초하여 임의 그래프에 NP-hard인 많은 그래프 최적화 문제를 경계가 있는 clique-width 그래프에서 빠르게 해결하거나 근사치를 구할 수 있다.
clique-width 개념의 기초가 되는 시공 순서는 1990년[1] Courcelle, Engelfriet, Rozenberg에 의해, Wanke(1994)에 의해 공식화되었다.클라이크 폭이라는 이름은 첼레비코바(1992)에 의해 다른 개념으로 사용되었다.1993년까지 이 용어는 이미 현재의 의미를 가지고 있었다.[2]
그래프의 특수 클래스
Cographs는 정확히 최대 2개의 clique-width를 가진 그래프다.[3]모든 거리-계통 그래프는 최대 3개의 클라이크 너비를 가진다.단, 단위 간격 그래프의 클라이크 너비는 (그들의 그리드 구조에 기초하여) 한이 없다.[4]마찬가지로, 초당적 순열 그래프의 클라이크 폭은 결합되지 않는다(유사한 그리드 구조에 기초함).[5]유도 서브그래프가 없는 그래프로서의 cographs의 특성화에 기초하여 4개의 정점을 가진 코드 없는 경로에 대한 이형성을 바탕으로, 금지된 유도 서브그래프에 의해 정의된 많은 그래프 클래스의 clique-width가 분류되었다.[6]
경계 클릭 너비가 있는 다른 그래프에는 k의 경계 값에 대한 k-leaf 검정력이 포함된다. 이는 그래프 검정력 T에k 있는 나무 T의 잎에 대한 유도 하위 그래프들이다.그러나 무한 지수를 가진 잎 권력은 한정된 클라이크 너비를 가지고 있지 않다.[7]
경계
Courcelle & Olariu(2000년)와 Corneil & Rotics(2005년)는 특정 그래프의 clique 너비에 대해 다음과 같은 한계를 입증했다.
- 그래프가 최대 k에서 클라이크 너비를 갖는 경우 그래프의 모든 유도 하위 그래프도 그러하다.[8]
- clique-width k 그래프의 보완 그래프는 최대 2k의 clique-width를 가진다.[9]
- 나무 너비 w의 그래프는 최대 3/2의w − 1 clique 너비를 가진다.이 경계에서 지수 의존성은 필요하다: 집단의 폭이 트리 너비보다 기하급수적으로 큰 그래프가 존재한다.[10]다른 방향에서, 경계된 clique-width의 그래프는 무한 트리 너비를 가질 수 있다. 예를 들어, n-vertex 전체 그래프는 clique-width 2를 가지지만 tree width n - 1을 가진다.그러나 완전한 초당적 그래프 K가t,t 서브그래프로 존재하지 않는 clique-width k의 그래프는 최대 3k(t - 1) - 1의 트리 너비를 가지고 있다. 따라서 희소성 그래프의 모든 계열에서 경계 트리 너비를 갖는 것은 경계된 clique-width를 갖는 것과 같다.[11]
- 또 다른 그래프 매개변수인 순위폭은 계급폭인 계급폭에 의해 양방향으로 경계를 이룬다: 계급폭인 ≤ ≤ cl 2rank-width + 1.[12]
또한 그래프 G에 clique 너비 k가 있으면 그래프 검정력 G에는c 최대 2kcc의k clique 너비가 있다.[13]트리 너비로부터 클라이크 너비에 대한 경계와 그래프 파워의 클라이크 너비에 대한 경계 둘 다 지수적인 차이가 있지만, 이러한 경계는 서로 화합하지 않는다: 그래프 G가 트리 너비 w를 갖는 경우, G는c 최대 2(w + 1c + 1) - 2에서 클라이크 너비를 가지며 트리 너비에 오직 단일 지수만을 가진다.[14]
계산 복잡성
더 일반적인 등급의 그래프에 대해 NP가 어려운 많은 최적화 문제는 이러한 그래프에 대한 구성 순서가 알려져 있을 때 경계된 clique-width 그래프에 동적 프로그래밍을 통해 효율적으로 해결될 수 있다.[15][16]특히 MSO1 단차 2차 논리(정점 집합에 대해 정량화를 허용하는 논리 형식)로 표현할 수 있는 모든 그래프 속성은 쿠셀의 정리 형식에 의해 경계된 클라이크 폭의 그래프에 대한 선형 시간 알고리즘을 가지고 있다.[16]
또한 구성 시퀀스를 알 수 있는 다항 시간 내에 경계 집단 폭의 그래프에 대해 최적의 그래프 색상이나 해밀턴 사이클을 찾을 수도 있지만, 다항식의 지수는 집단 폭과 함께 증가하며, 계산 복잡성 이론의 증거는 이러한 의존성이 필요할 가능성이 있음을 보여준다.[17]경계가 있는 clique-width의 그래프는 χ 경계로 되어 있는데, 이는 그들의 색수가 기껏해야 가장 큰 clique 크기의 함수라는 것을 의미한다.[18]
clique-width 3의 그래프는 분할 분해에 기반한 알고리즘을 사용하여 다항 시간 내에 인식될 수 있으며, 이들을 위한 구성 시퀀스를 찾을 수 있다.[19]무한 클라이크 너비의 그래프의 경우, 클라이크 너비를 정확하게 계산하는 것은 NP-hard이며, 또한 NP-hardiable 적층 오차를 갖는 근사치를 구하는 것도 NP-hard이다.[20]그러나, clique-width를 경계로 할 때, 다항 시간 내에 경계폭(실제 clique-width보다 훨씬 큰)의 시공 순서를 얻을 수 있다.[21]정확한 clique-width 또는 그것에 대한 더 엄격한 근사치가 고정 매개변수 추적 가능한 시간으로 계산될 수 있는지, clique-width에 고정된 모든 경계에 대해 다항 시간에서 계산할 수 있는지, 또는 심지어 clique-width 4의 그래프를 다항 시간에서 인식할 수 있는지 여부도 열린 채로 있다.[20]
트리 너비에 대한 관계
경계 클라이크 폭의 그래프 이론은 경계 트리 폭의 그래프와 유사하지만, 트리 폭과 달리 밀도가 높은 그래프를 허용한다.그래프 패밀리의 범위를 경계로 한 경우, 경계 트리 너비를 갖거나 모든 완전한 양분 그래프는 패밀리의 그래프의 하위 그래프일 수 있다.[11]트리 너비와 클라이크 너비는 선 그래프 이론을 통해서도 연결된다. 즉, 선 그래프가 클라이크 너비를 경계한 경우에만 그래프의 한 계열이 경계 트리 너비를 가진다.[22]
메모들
- ^ Courcelle, Engelfriet & Rozenberg (1993년).
- ^ 쿠르셀(1993년).
- ^ 쿠르셀 & 올라리우(2000년)
- ^ 골룸빅&로틱스(2000년)
- ^ Brandstédt & Lozin(2003년).
- ^ 브란슈타트 외 (2005); Brandsteht 등 (2006).
- ^ Brandstédt & Hundt(2008);구르스키&완케(2009년).
- ^ Courcelle & Olariu(2000), Corollary 3.3.
- ^ Courcelle & Olariu(2000),정리 4.1.
- ^ Corneil & Rotics(2005), Courcel & Olariu 강화(2000),정리 5.5.
- ^ a b 구르스키&완케(2000년).
- ^ 옴앤세이모어(2006년).
- ^ 토딘카(2003년).
- ^ 구르스키&완케(2009년).
- ^ 코기스 앤 티에리(2005년).
- ^ a b Courcelle, Makowsky & Rotics(2000).
- ^ 포민 외 연구진(2010년).
- ^ 드보르자크 & 크랄' (2012).
- ^ Corneil 외 연구진(2012).
- ^ a b 펠로우즈 외 (2009).
- ^ 옴 & 시모어(2006);Hliněný & Oum(2008);오움(2009년).
- ^ 구르스키&완케(2007)
참조
- Brandstädt, A.; Dragan, F.F.; Le, H.-O.; Mosca, R. (2005), "New graph classes of bounded clique-width", Theory of Computing Systems, 38 (5): 623–645, CiteSeerX 10.1.1.3.5994, doi:10.1007/s00224-004-1154-6, S2CID 2309695.
- Brandstädt, A.; Engelfriet, J.; Le, H.-O.; Lozin, V.V. (2006), "Clique-width for 4-vertex forbidden subgraphs", Theory of Computing Systems, 39 (4): 561–590, doi:10.1007/s00224-005-1199-1, S2CID 20050455.
- Brandstädt, Andreas; Hundt, Christian (2008), "Ptolemaic graphs and interval graphs are leaf powers", LATIN 2008: Theoretical informatics, Lecture Notes in Comput. Sci., vol. 4957, Springer, Berlin, pp. 479–491, doi:10.1007/978-3-540-78773-0_42, MR 2472761.
- Brandstädt, A.; Lozin, V.V. (2003), "On the linear structure and clique-width of bipartite permutation graphs", Ars Combinatoria, 67: 273–281, CiteSeerX 10.1.1.16.2000.
- Chlebíková, J. (1992), "On the tree-width of a graph", Acta Mathematica Universitatis Comenianae, New Series, 61 (2): 225–236, CiteSeerX 10.1.1.30.3900, MR 1205875.
- Cogis, O.; Thierry, E. (2005), "Computing maximum stable sets for distance-hereditary graphs", Discrete Optimization, 2 (2): 185–188, doi:10.1016/j.disopt.2005.03.004, MR 2155518.
- Corneil, Derek G.; Habib, Michel; Lanlignel, Jean-Marc; Reed, Bruce; Rotics, Udi (2012), "Polynomial-time recognition of clique-width ≤ 3 graphs", Discrete Applied Mathematics, 160 (6): 834–865, doi:10.1016/j.dam.2011.03.020, MR 2901093.
- Corneil, Derek G.; Rotics, Udi (2005), "On the relationship between clique-width and treewidth", SIAM Journal on Computing, 34 (4): 825–847, doi:10.1137/S0097539701385351, MR 2148860.
- Courcelle, Bruno; Engelfriet, Joost; Rozenberg, Grzegorz (1993), "Handle-rewriting hypergraph grammars", Journal of Computer and System Sciences, 46 (2): 218–270, doi:10.1016/0022-0000(93)90004-G, MR 1217156. Graph Grammars 및 컴퓨터 과학에 대한 적용(Bremen, 1990), MR1431281에 예비 형태로 제시된다.
- Courcelle, B. (1993), "Monadic second-order logic and hypergraph orientation", Proceedings of Eighth Annual IEEE Symposium on Logic in Computer Science (LICS '93), pp. 179–190, doi:10.1109/LICS.1993.287589, S2CID 39254668.
- Courcelle, B.; Makowsky, J. A.; Rotics, U. (2000), "Linear time solvable optimization problems on graphs on bounded clique width", Theory of Computing Systems, 33 (2): 125–150, CiteSeerX 10.1.1.414.1845, doi:10.1007/s002249910009, S2CID 15402031.
- Courcelle, B.; Olariu, S. (2000), "Upper bounds to the clique width of graphs", Discrete Applied Mathematics, 101 (1–3): 77–144, doi:10.1016/S0166-218X(99)00184-5.
- Dvořák, Zdeněk; Král', Daniel (2012), "Classes of graphs with small rank decompositions are χ-bounded", Electronic Journal of Combinatorics, 33 (4): 679–683, arXiv:1107.2161, doi:10.1016/j.ejc.2011.12.005, S2CID 5530520
- Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan (2009), "Clique-width is NP-complete", SIAM Journal on Discrete Mathematics, 23 (2): 909–939, doi:10.1137/070687256, MR 2519936.
- Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket (2010), "Intractability of clique-width parameterizations", SIAM Journal on Computing, 39 (5): 1941–1956, CiteSeerX 10.1.1.220.1712, doi:10.1137/080742270, MR 2592039.
- Golumbic, Martin Charles; Rotics, Udi (2000), "On the clique-width of some perfect graph classes", International Journal of Foundations of Computer Science, 11 (3): 423–443, doi:10.1142/S0129054100000260, MR 1792124.
- Gurski, 프랭크, 왕케, 에곤(2000년),"clique-width의 tree-width Kn,n 없이 그래프로 껑충껑충 내달렸다.", Brandes, Ulrik에;바그너, 도로시아(eds.), Graph-Theoretic 개념 컴퓨터 과학으로:26일 국제 워크숍 WG 2000년 콘스탄츠, 독일, 6월 15–17, 2000, 회보, 강의 노트 컴퓨터 과학으로, 1928년 vol., 베를린:스프링거,를 대신하여 서명함. 196–20.5, doi:10.1007/3-540-40064-8_19, MR1850348.
- Gurski, Frank; Wanke, Egon (2007), "Line graphs of bounded clique-width", Discrete Mathematics, 307 (22): 2734–2754, doi:10.1016/j.disc.2007.01.020.
- Gurski, Frank; Wanke, Egon (2009), "The NLC-width and clique-width for powers of graphs of bounded tree-width", Discrete Applied Mathematics, 157 (4): 583–595, doi:10.1016/j.dam.2008.08.031, MR 2499471.
- Hliněný, Petr; Oum, Sang-il (2008), "Finding branch-decompositions and rank-decompositions", SIAM Journal on Computing, 38 (3): 1012–1032, CiteSeerX 10.1.1.94.2272, doi:10.1137/070685920, MR 2421076.
- Oum, Sang-il; Seymour, Paul (2006), "Approximating clique-width and branch-width", Journal of Combinatorial Theory, Series B, 96 (4): 514–528, doi:10.1016/j.jctb.2005.10.006, MR 2232389.
- Oum, Sang-il (2009), "Approximating rank-width and clique-width quickly", ACM Transactions on Algorithms, Lecture Notes in Computer Science, 5 (1): Art. 10, 20, CiteSeerX 10.1.1.574.8156, doi:10.1007/11604686_5, ISBN 978-3-540-31000-6, MR 2479181.
- Todinca, Ioan (2003), "Coloring powers of graphs of bounded clique-width", Graph-theoretic concepts in computer science, Lecture Notes in Comput. Sci., vol. 2880, Springer, Berlin, pp. 370–382, doi:10.1007/978-3-540-39890-5_32, MR 2080095.
- Wanke, Egon (1994), "k-NLC graphs and polynomial algorithms", Discrete Applied Mathematics, 54 (2–3): 251–266, doi:10.1016/0166-218X(94)90026-4, MR 1300250.
