stringtranslate.com

ancho de camarilla

Construcción de un gráfico hereditario de distancia de ancho de camarilla 3 mediante uniones disjuntas, reetiquetados y uniones de etiquetas. Las etiquetas de vértice se muestran como colores.

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:

  1. Creación de un nuevo vértice v con etiqueta i (denotado por i ( v ) )
  2. Unión disjunta de dos gráficos etiquetados G y H (indicados por )
  3. Uniendo por una arista cada vértice etiquetado i con cada vértice etiquetado j (denotado por η ( i , j ) ), donde i ≠ j
  4. 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:

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?

(más problemas sin resolver en matemáticas)

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

  1. ^ Courcelle, Engelfriet y Rozenberg (1993).
  2. ^ Courcelle (1993).
  3. ^ Courcelle y Olariu (2000).
  4. ^ Golumbic y Róticos (2000).
  5. ^ Brandstädt y Lozin (2003).
  6. ^ Brandstädt y col. (2005); Brandstädt et al. (2006).
  7. ^ Brandstädt y Hundt (2008); Gurski y Wanke (2009).
  8. ^ Courcelle y Olariu (2000), Corolario 3.3.
  9. ^ Courcelle y Olariu (2000), Teorema 4.1.
  10. ^ Corneil & Rotics (2005), fortaleciendo Courcelle & Olariu (2000), Teorema 5.5.
  11. ^ ab Gurski y Wanke (2000).
  12. ^ Oum y Seymour (2006).
  13. ^ Todinca (2003).
  14. ^ Gurski y Wanke (2009).
  15. ^ Cogis y Thierry (2005).
  16. ^ ab Courcelle, Makowsky y Rotics (2000).
  17. ^ Fomín y col. (2010).
  18. ^ Dvořák y Král' (2012).
  19. ^ Corneil y col. (2012).
  20. ^ ab Fellows y otros. (2009).
  21. ^ Oum y Seymour (2006); Hliněný y Oum (2008); Oum (2008); Fomín y Korhonen (2022).
  22. ^ Fomín y Korhonen (2022).
  23. ^ Gurski y Wanke (2007).
  24. ^ Capo y col. (2022).

Referencias