En teoría de grafos , el ancho de camarilla de un gráfico G es un parámetro que describe la complejidad estructural del gráfico; está estrechamente relacionado con el ancho del árbol , pero a diferencia del ancho del árbol, puede ser pequeño para gráficos densos . Se define como el número mínimo de etiquetas necesarias para construir G mediante las siguientes 4 operaciones:
Creación de un nuevo vértice v con etiqueta i (denotado por i ( v ) )
Unión disjunta de dos gráficos etiquetados G y H (indicados por )
Uniendo por una arista cada vértice etiquetado i con cada vértice etiquetado j (denotado por η ( i , j ) ), donde i ≠ j
Cambiar el nombre de la etiqueta i a la etiqueta j (indicada por ρ ( i , j ) )
Los gráficos de ancho de camarilla acotado incluyen los cografos y los gráficos hereditarios de distancia . Aunque es NP-difícil calcular el ancho de camarilla cuando no está acotado, y se desconoce si se puede calcular en tiempo polinómico cuando está acotado, se conocen algoritmos de aproximación eficientes para el ancho de 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 se pueden resolver o aproximar rápidamente en 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). Chlebíková (1992) utilizó el nombre "ancho de camarilla" para un concepto diferente. En 1993 el término ya tenía su significado actual. [2]
Clases especiales de gráficos.
Los cografos son exactamente los gráficos con un ancho de camarilla como máximo de 2. [3]
Cada gráfico hereditario de distancia tiene un ancho de camarilla como máximo de 3. Sin embargo, el ancho de camarilla de los gráficos de intervalo unitario es ilimitado (según su estructura de cuadrícula). [4]
De manera similar, el ancho de camarilla de los gráficos de permutación bipartitos es ilimitado (basado en una estructura de cuadrícula similar). [5]
Basado en la caracterización de los cografos como gráficos sin subgrafos inducidos isomórficos a una ruta con cuatro vértices, se ha clasificado el ancho de camarilla de muchas clases de gráficos definidas por subgrafos inducidos prohibidos. [6]
Otros gráficos con ancho de camarilla acotado incluyen las k potencias de hoja para valores acotados de k ; estos son los subgrafos inducidos de las hojas de un árbol T en la potencia del gráfico T k . Sin embargo, las potencias de las hojas con exponentes ilimitados no tienen un ancho de camarilla limitado. [7]
Límites
Courcelle y Olariu (2000) y Corneil y Rotics (2005) demostraron los siguientes límites en el ancho de camarilla de ciertos gráficos:
Si un gráfico tiene un ancho de camarilla como máximo k , entonces también lo tiene cada subgrafo inducido del gráfico. [8]
El gráfico complementario de un gráfico 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 camarilla 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 subgrafo 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 ancho de rango , está limitado en ambas direcciones por el ancho de camarilla: ancho de rango ≤ ancho de camarilla ≤ 2 ancho de rango + 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 de 2 kc k . [13] Aunque existe una brecha exponencial tanto en el límite para el ancho de camarilla del ancho del árbol como en el límite para el ancho de 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
Problema no resuelto en matemáticas :
¿Se pueden reconocer gráficas de ancho de camarilla acotado en tiempo polinómico?
Muchos problemas de optimización que son NP-difíciles para clases de gráficos más generales pueden resolverse eficientemente mediante 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 coloraciones de gráficos óptimas 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]
Las gráficas de ancho de camarilla acotadas están acotadas por χ , lo que significa que su número cromático es como máximo una función del tamaño de su camarilla más grande. [18]
Las gráficas de ancho de camarilla tres se pueden reconocer y encontrar una secuencia de construcción para ellas, en tiempo polinomial usando un algoritmo basado en descomposición dividida . [19]
Para gráficos de ancho de camarilla ilimitado, es NP-difícil calcular el ancho de camarilla exactamente, 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 mayor que el ancho de la camarilla real) en tiempo polinómico, [21] en particular en tiempo cuadrático en el número de vértices. [22] Queda por decidir si el ancho de camarilla exacto, o una aproximación más estricta a él, puede calcularse en tiempo manejable con parámetros fijos , si puede calcularse en tiempo polinómico para cada límite fijo en el ancho de camarilla, o incluso si las gráficas del ancho de camarilla cuatro se pueden reconocer en tiempo polinomial. [20]
Parámetros de ancho relacionados
La teoría de los gráficos de ancho de camarilla 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 camarilla limitado, entonces tiene un ancho de árbol limitado o cada gráfico bipartito completo es un subgrafo de un gráfico de la familia. [11] El ancho de árbol y el ancho de 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 acotado si y sólo si sus gráficos lineales tienen un ancho de camarilla acotado. [23]
Las gráficas de ancho de camarilla acotado también tienen ancho gemelo acotado . [24]
Notas
^ Courcelle, Engelfriet y Rozenberg (1993).
^ Courcelle (1993).
^ Courcelle y Olariu (2000).
^ Golumbic y Róticos (2000).
^ Brandstädt y Lozin (2003).
^ Brandstädt y col. (2005); Brandstädt et al. (2006).
^ Brandstädt y Hundt (2008); Gurski y Wanke (2009).
^ Oum y Seymour (2006); Hliněný y Oum (2008); Oum (2008); Fomín y Korhonen (2022).
^ Fomín y Korhonen (2022).
^ Gurski y Wanke (2007).
^ Capo y col. (2022).
Referencias
Bonnet, Édouard; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2022), "Twin-width I: Comprobación del modelo FO manejable", Journal of the ACM , 69 (1): A3:1–A3:46, arXiv : 2004.14789 , doi :10.1145/3486655, MR 4402362
Brandstädt, A .; Dragan, FF; Le, H.-O.; Mosca, R. (2005), "Nuevas clases de gráficos de ancho de camarilla acotado", Teoría de 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 sistemas informáticos , 39 (4): 561–590, doi :10.1007/s00224-005-1199-1, S2CID 20050455.
Brandstädt, Andreas; Hundt, Christian (2008), "Los gráficos ptolemaicos y los gráficos de intervalo son potencias de hoja", LATIN 2008: Informática teórica , Lecture Notes in Comput. Ciencia, vol. 4957, Springer, Berlín, págs. 479–491, doi :10.1007/978-3-540-78773-0_42, SEÑOR 2472761.
Brandstädt, A .; Lozin, VV (2003), "Sobre la estructura lineal y el ancho de camarilla de gráficos de permutación bipartitos", Ars Combinatoria , 67 : 273–281, CiteSeerX 10.1.1.16.2000.
Chlebíková, J. (1992), "Sobre el ancho del árbol de un gráfico", Acta Mathematica Universitatis Comenianae , New Series, 61 (2): 225–236, CiteSeerX 10.1.1.30.3900 , MR 1205875.
Cogis, O.; Thierry, E. (2005), "Cálculo de conjuntos estables máximos para gráficos hereditarios de distancia", 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; Caña, Bruce ; Rotics, Udi (2012), "Reconocimiento en tiempo polinomial 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 camarilla y el ancho de á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áticas gráficas y su aplicación a la informática (Bremen, 1990), MR 1431281.
Courcelle, B. (1993), "Lógica monádica de segundo orden y orientación hipergráfica", Actas del octavo simposio anual del IEEE sobre lógica en informática (LICS '93) , págs. 179-190, doi :10.1109/LICS.1993.287589, S2CID 39254668.
Courcelle, B .; Makowsky, JA ; Rotics, U. (2000), "Problemas de optimización resolubles en tiempo lineal en gráficos con ancho de camarilla acotado", Teoría de 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 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 limitadas por χ", Electronic Journal of Combinatorics , 33 (4): 679–683, arXiv : 1107.2161 , doi :10.1016/j.ejc.2011.12. 005, S2CID 5530520
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket (2010), "Intratabilidad de las parametrizaciones de ancho de camarilla", SIAM Journal on Computing , 39 (5): 1941–1956, CiteSeerX 10.1.1.220.1712 , doi :10.1137/080742270, MR 2592039.
Fomin, Fedor V.; Korhonen, Tuukka (2022), "Aproximación rápida de FPT al ancho de rama", Actas del 54º Simposio anual ACM SIGACT sobre teoría de la informática , ACM, págs. 886–899, arXiv : 2111.03492 , doi : 10.1145/3519935.3519996, S2CID 24 3832882.
Golumbic, Martín Carlos ; Rotics, Udi (2000), "Sobre el ancho de camarilla de algunas clases de gráficos perfectos", Revista Internacional de Fundamentos de Ciencias de la Computación , 11 (3): 423–443, doi :10.1142/S0129054100000260, MR 1792124.
Gurski, Frank; Wanke, Egon (2000), "El ancho de árbol de gráficos acotados de ancho de camarilla sin K n, n ", en Brandes, Ulrik ; Wagner, Dorothea (eds.), Conceptos teóricos de grafos en informática: 26º taller internacional, WG 2000, Konstanz, Alemania, 15 al 17 de junio de 2000, Actas , Lecture Notes in Computer Science, vol. 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 de líneas 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 camarilla para potencias de gráficos de ancho de árbol acotado", Matemáticas Aplicadas Discretas , 157 (4): 583–595, doi : 10.1016/j.dam.2008.08. 031 , señor 2499471.
Hliněný, Petr; Oum, Sang-il (2008), "Encontrar descomposiciones de ramas y descomposiciones de rangos", SIAM Journal on Computing , 38 (3): 1012–1032, CiteSeerX 10.1.1.94.2272 , doi :10.1137/070685920, MR 2421076.
Todinca, Ioan (2003), "Poderes de coloración de gráficos de ancho de camarilla acotado", Conceptos de teoría de grafos en informática , Apuntes de conferencias sobre informática. Ciencia, vol. 2880, Springer, Berlín, págs. 370–382, doi :10.1007/978-3-540-39890-5_32, SEÑOR 2080095.
Wanke, Egon (1994), " k -NLC gráficos y algoritmos polinomiales", Matemáticas aplicadas discretas , 54 (2–3): 251–266, doi : 10.1016/0166-218X(94)90026-4 , SEÑOR 1300250.