En teoría de grafos , el ancho de camarilla de un grafo es un parámetro que describe la complejidad estructural del gráfico; está estrechamente relacionado con el ancho de árbol , pero a diferencia del ancho de árbol, puede estar acotado incluso para gráficos densos . Se define como el número mínimo de etiquetas necesarias para construir mediante las siguientes 4 operaciones:
- Creación de un nuevo vértice v con etiqueta i (anotado i (v) )
- Unión disjunta de dos gráficos etiquetados G y H (denotados )
- Uniendo por una arista cada vértice etiquetado i a cada vértice etiquetado j (denotado η (i, j) ), donde
- Cambiar el nombre de la etiqueta i a la etiqueta j (denotado ρ ( i , j ))
Los gráficos de ancho de camarilla acotado incluyen los gráficos cográficos y los gráficos de distancia hereditaria . Aunque es NP-difícil calcular el ancho de la camarilla cuando no está acotado, y se desconoce si se puede calcular en tiempo polinomial cuando está acotado, se conocen algoritmos de aproximación eficientes para el ancho de la camarilla. Con base en estos algoritmos y en el teorema de Courcelle , muchos problemas de optimización de gráficos que son NP-difíciles para gráficos arbitrarios pueden resolverse o aproximarse rápidamente en los gráficos de ancho de camarilla acotado.
Las secuencias de construcción que subyacen al concepto de ancho de camarilla fueron formuladas por Courcelle , Engelfriet y Rozenberg en 1990 [1] y por Wanke (1994) . El nombre "ancho de camarilla" fue utilizado para un concepto diferente por Chlebíková (1992) . En 1993, el término ya tenía su significado actual. [2]
Clases especiales de gráficos
Los cographs son exactamente los gráficos con un ancho de camarilla como máximo 2. [3] Cada gráfico hereditario de distancia tiene un ancho de camarilla como máximo 3. Sin embargo, el ancho de camarilla de los gráficos de intervalo unitario es ilimitado (basado en su estructura de cuadrícula). [4] De manera similar, el ancho de la camarilla de los gráficos de permutación bipartita es ilimitado (basado en una estructura de cuadrícula similar). [5] Con base en la caracterización de las cografías como las gráficas sin subgrafias inducidas isomorfas a una trayectoria sin cuerda con cuatro vértices, se ha clasificado el ancho de la camarilla de muchas clases de grafos definidos por subgrafias inducidas prohibidas. [6]
Otros gráficos con ancho de camarilla acotado incluyen las potencias de la hoja k para valores acotados de k ; estos son los subgrafos inducidos de las hojas de un árbol T en el gráfico de potencia T k . Sin embargo, los poderes de las hojas con exponentes ilimitados no tienen un ancho de camarilla limitado. [7]
Límites
Courcelle & Olariu (2000) y Corneil & Rotics (2005) demostraron los siguientes límites en el ancho de la camarilla de ciertos gráficos:
- Si un gráfico tiene un ancho de clique como máximo k , también lo tiene cada subgráfico inducido del gráfico. [8]
- La gráfica de complemento de una gráfica de ancho de camarilla k tiene un ancho de camarilla como máximo 2 k . [9]
- Las gráficas de ancho de árbol w tienen un ancho de camarilla como máximo 3 · 2 w - 1 . La dependencia exponencial en este límite es necesaria: existen gráficos cuyo ancho de camarilla es exponencialmente mayor que el ancho de su árbol. [10] En la otra dirección, los gráficos de ancho de camarilla acotado pueden tener un ancho de árbol ilimitado; por ejemplo, los gráficos completos de n - vértices tienen un ancho de clique 2 pero un ancho de árbol n - 1 . Sin embargo, los gráficos de ancho de camarilla k que no tienen un gráfico bipartito completo K t , t como subgráfico tienen un ancho de árbol como máximo 3 k ( t - 1) - 1 . Por lo tanto, para cada familia de gráficos dispersos , tener un ancho de árbol acotado es equivalente a tener un ancho de camarilla acotado. [11]
- Otro parámetro del gráfico, el rango-ancho , está limitado en ambas direcciones por el ancho de la camarilla: rango-ancho ≤ ancho de la camarilla ≤ 2 rango-ancho + 1 . [12]
Además, si un gráfico G tiene un ancho de camarilla k , entonces la potencia del gráfico G c tiene un ancho de camarilla como máximo 2 kc k . [13] Aunque existe una brecha exponencial tanto en el límite para el ancho de la camarilla del ancho del árbol como en el límite para el ancho de la camarilla de las potencias del gráfico, estos límites no se componen entre sí: si un gráfico G tiene un ancho de árbol w , entonces G c tiene ancho de camarilla como máximo 2 ( c + 1) w + 1 - 2 , solo exponencial individualmente en el ancho del árbol. [14]
Complejidad computacional
¿Se pueden reconocer gráficos de ancho de camarilla acotado en tiempo polinomial?
Muchos problemas de optimización que son NP-difíciles para clases más generales de gráficos pueden resolverse de manera eficiente mediante la programación dinámica en gráficos de ancho de camarilla acotado, cuando se conoce una secuencia de construcción para estos gráficos. [15] [16] En particular, cada propiedad de gráfico que se puede expresar en lógica monádica de segundo orden MSO 1 (una forma de lógica que permite la cuantificación sobre conjuntos de vértices) tiene un algoritmo de tiempo lineal para gráficos de ancho de camarilla acotado, por una forma del teorema de Courcelle . [dieciséis]
También es posible encontrar colores de gráficos óptimos o ciclos hamiltonianos para gráficos de ancho de camarilla acotado en tiempo polinomial, cuando se conoce una secuencia de construcción, pero el exponente del polinomio aumenta con el ancho de camarilla, y la evidencia de la teoría de la complejidad computacional muestra que esta dependencia probablemente sea necesaria. [17] Los gráficos de acotada clique ancho son χ -bounded , lo que significa que su número cromática es a lo sumo una función del tamaño de su más grande clique. [18]
Se pueden reconocer los gráficos de tres de ancho de camarilla, y se puede encontrar una secuencia de construcción para ellos, en tiempo polinomial utilizando un algoritmo basado en la descomposición dividida . [19] Para gráficos de ancho de camarilla ilimitado, es NP-difícil calcular exactamente el ancho de camarilla, y también NP-difícil obtener una aproximación con error aditivo sublineal. [20] Sin embargo, cuando el ancho de la camarilla está acotado, es posible obtener una secuencia de construcción de ancho acotado (exponencialmente más grande que el ancho real de la camarilla) en tiempo polinomial. [21] Queda abierto si el ancho exacto de la camarilla, o una aproximación más estricta a él, se puede calcular en un tiempo manejable de parámetro fijo , si se puede calcular en tiempo polinomial para cada límite fijo en el ancho de la camarilla, o incluso si las gráficas de cuatro de ancho de camarilla pueden reconocerse en tiempo polinomial. [20]
Relación con el ancho del árbol
La teoría de los gráficos de ancho de pandilla acotado se parece a la de los gráficos de ancho de árbol acotado , pero a diferencia del ancho de árbol permite gráficos densos . Si una familia de gráficos tiene un ancho de clique limitado, entonces o tiene un ancho de árbol limitado o cada gráfico bipartito completo es un subgráfico de un gráfico de la familia. [11] El ancho del árbol y el ancho de la camarilla también están conectados a través de la teoría de los gráficos lineales : una familia de gráficos tiene un ancho de árbol limitado si y solo si sus gráficos lineales tienen un ancho limitado de la camarilla. [22]
Notas
- ^ Courcelle, Engelfriet y Rozenberg (1993) .
- ^ Courcelle (1993) .
- ^ Courcelle y Olariu (2000) .
- ^ Golumbic y Rotics (2000) .
- ^ Brandstädt y Lozin (2003) .
- ^ Brandstädt y col. (2005) ; Brandstädt y col. (2006) .
- ^ Brandstädt y Hundt (2008) ; Gurski y Wanke (2009) .
- ^ Courcelle y Olariu (2000) , Corolario 3.3.
- ^ Courcelle y Olariu (2000) , Teorema 4.1.
- ^ Corneil y Rotics (2005) , fortalecimiento de Courcelle y Olariu (2000) , Teorema 5.5.
- ↑ a b Gurski y Wanke (2000) .
- ^ Oum y Seymour (2006) .
- ^ Todinca (2003) .
- ^ Gurski y Wanke (2009) .
- ^ Cogis y Thierry (2005) .
- ↑ a b Courcelle, Makowsky y Rotics (2000) .
- ^ Fomin y col. (2010) .
- ^ Dvořák y Král '(2012) .
- ^ Corneil y col. (2012) .
- ^ a b Fellows et al. (2009) .
- ^ Oum y Seymour (2006) ; Hliněný y Oum (2008) ; Oum (2009) .
- ^ Gurski y Wanke (2007) .
Referencias
- Brandstädt, A .; Dragan, FF; Le, H.-O .; Mosca, R. (2005), "Nuevas clases de gráficos de ancho de camarilla acotado", Teoría de los sistemas informáticos , 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, VV (2006), "Ancho de camarilla para subgrafos prohibidos de 4 vértices", Teoría de los sistemas informáticos , 39 (4): 561–590, doi : 10.1007 / s00224-005-1199-1 , S2CID 20050455.
- Brandstädt, Andreas; Hundt, Christian (2008), "Las gráficas ptolemaicas y las gráficas de intervalo son poderes foliares", LATIN 2008: Informática teórica , Lecture Notes in Comput. Sci., 4957 , Springer, Berlín, págs. 479–491, doi : 10.1007 / 978-3-540-78773-0_42 , MR 2472761.
- Brandstädt, A .; Lozin, VV (2003), "Sobre la estructura lineal y el ancho de camarilla de los gráficos de permutación bipartita", 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), "Computación de conjuntos estables máximos para gráficos de distancia-hereditarios", Optimización discreta , 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), "Reconocimiento en tiempo polinómico de ancho de camarilla ≤ 3 gráficos", Matemáticas aplicadas discretas , 160 (6): 834–865, doi : 10.1016 / j.dam.2011.03.020 , MR 2901093.
- Corneil, Derek G .; Rotics, Udi (2005), "Sobre la relación entre el ancho de la camarilla y el ancho del árbol", 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. Presentado en forma preliminar en Gramática gramáticas y su aplicación a la informática (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, JA ; Rotics, U. (2000), "Problemas de optimización con solución en tiempo lineal en gráficos de ancho de camarilla acotado", Teoría de los sistemas informáticos , 33 (2): 125–150, CiteSeerX 10.1.1.414.1845 , doi : 10.1007 / s002249910009 , S2CID 15402031.
- Courcelle, B .; Olariu, S. (2000), " Límites superiores del ancho de la camarilla de los gráficos" , Matemáticas aplicadas discretas , 101 (1–3): 77–144, doi : 10.1016 / S0166-218X (99) 00184-5.
- Dvořák, Zdeněk; Král ', Daniel (2012), "Las clases de gráficos con descomposiciones de rango pequeño están acotadas por χ", Electronic Journal of Combinatorics , 33 (4): 679–683, arXiv : 1107.2161 , doi : 10.1016 / j.ejc.2011.12. 005 , S2CID 5530520
- Becarios, 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 parametrizaciones", 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, Frank; Wanke, Egon (2000), "El ancho de árbol de los gráficos acotados de ancho de camarilla sin K n, n ", en Brandes, Ulrik; Wagner, Dorothea (eds.), Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000, Konstanz, Alemania, 15-17 de junio de 2000, Actas , Lecture Notes in Computer Science, 1928 , Berlín: Springer, págs. 196–205, doi : 10.1007 / 3-540-40064-8_19 , MR 1850348.
- Gurski, Frank; Wanke, Egon (2007), "Gráficos lineales de ancho de camarilla acotado", Matemáticas discretas , 307 (22): 2734-2754, doi : 10.1016 / j.disc.2007.01.020.
- Gurski, Frank; Wanke, Egon (2009), "El ancho NLC y el ancho de la camarilla para potencias de gráficos de ancho de árbol acotado", 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-descompositions 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), "Aproximación del ancho de la camarilla y el ancho de la rama", Journal of Combinatorial Theory , Serie B, 96 (4): 514-528, doi : 10.1016 / j.jctb.2005.10.006 , MR 2232389.
- Oum, Sang-il (2009), "Aproximación rápida del ancho de rango y el ancho de la camarilla", Transacciones ACM sobre algoritmos , Notas de conferencias en Ciencias de la Computación, 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), "Los poderes de coloración de gráficos de ancho de camarilla acotado", Conceptos de teoría de gráficos en informática , Lecture Notes in Comput. Sci., 2880 , Springer, Berlín, págs. 370–382, doi : 10.1007 / 978-3-540-39890-5_32 , MR 2080095.
- Wanke, Egon (1994), " k- NLC gráficas y algoritmos polinomiales", Matemáticas aplicadas discretas , 54 (2–3): 251–266, doi : 10.1016 / 0166-218X (94) 90026-4 , MR 1300250.