stringtranslate.com

Ancho de camarilla

Construcción de un grafo hereditario de distancia con un ancho de clique 3 mediante uniones disjuntas, reetiquetados y uniones de etiquetas. Las etiquetas de los vértices se muestran en colores.

En teoría de grafos , el ancho de grupo de un grafo G es un parámetro que describe la complejidad estructural del grafo; está estrechamente relacionado con el ancho de árbol , pero a diferencia de este último puede ser pequeño para grafos 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 (denotados por )
  3. Uniendo mediante 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 (denotada 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 grafos que son NP-difíciles para grafos arbitrarios se pueden resolver o aproximar rápidamente en los grafos de ancho de camarilla acotado.

Las secuencias de construcción que sustentan el concepto de amplitud de camarilla fueron formuladas por Courcelle , Engelfriet y Rozenberg en 1990 [1] y por Wanke (1994). El nombre "anchura 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 cografos son exactamente los grafos con un ancho de camarilla de como máximo 2. [3] Cada grafo hereditario de distancia tiene un ancho de camarilla de como máximo 3. Sin embargo, el ancho de camarilla de los grafos de intervalo unitario no tiene límites (según su estructura de cuadrícula). [4] De manera similar, el ancho de camarilla de los grafos de permutación bipartitos no tiene límites (según una estructura de cuadrícula similar). [5] Con base en la caracterización de los cografos como los grafos sin subgrafo inducido isomorfos a un camino con cuatro vértices, se ha clasificado el ancho de camarilla de muchas clases de grafos definidas por subgrafos inducidos prohibidos. [6]

Otros gráficos con un ancho de camarilla acotado incluyen las potencias de k -hojas para valores acotados de k ; estos son los subgrafos inducidos de las hojas de un árbol T en la potencia gráfica T k . Sin embargo, las potencias de hojas con exponentes no acotados no tienen un ancho de camarilla acotado. [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 grafo G tiene un ancho de camarilla k , entonces la potencia del grafo G c tiene un ancho de camarilla como máximo 2 kc k . [13] Aunque hay 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 grafo, estos límites no se componen entre sí: si un grafo G tiene un ancho de árbol w , entonces G c tiene un ancho de camarilla como máximo 2( c + 1) w + 1 − 2 , solo exponencialmente simple en el ancho del árbol. [14]

Complejidad computacional

Problema sin resolver en matemáticas :
¿Es posible reconocer gráficos con ancho de camarilla acotado en tiempo polinomial?
(más problemas sin resolver en matemáticas)

Muchos problemas de optimización que son NP-difíciles para clases más generales de gráficos se pueden resolver de manera eficiente 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, mediante una forma del teorema de Courcelle . [16]

También es posible encontrar coloraciones de grafos óptimas o ciclos hamiltonianos para grafos 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 es probable que esta dependencia sea necesaria. [17] Los grafos de ancho de camarilla acotado están acotados 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]

Los gráficos de ancho de camarilla tres se pueden reconocer, y se puede encontrar una secuencia de construcción para ellos, 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 camarilla está acotado, es posible obtener una secuencia de construcción de ancho acotado (exponencialmente mayor que el ancho de camarilla real) en tiempo polinomial, [21] en particular en tiempo cuadrático en el número de vértices. [22] Queda abierto si el ancho de camarilla exacto, o una aproximación más estricta al mismo, se puede calcular en tiempo manejable con parámetros fijos , si se puede calcular en tiempo polinomial para cada límite fijo en el ancho de camarilla, o incluso si los gráficos del ancho de camarilla cuatro se pueden reconocer en tiempo polinomial. [20]

Parámetros de ancho relacionados

La teoría de grafos de ancho de camarilla acotado se parece a la de grafos de ancho de árbol acotado , pero a diferencia del ancho de árbol permite grafos densos . Si una familia de grafos tiene un ancho de camarilla acotado, entonces o bien tiene un ancho de árbol acotado o bien cada grafo bipartito completo es un subgrafo de un grafo 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 grafos lineales : una familia de grafos tiene un ancho de árbol acotado si y solo si sus grafos lineales tienen un ancho de camarilla acotado. [23]

Los gráficos de ancho de camarilla acotado también tienen ancho de gemelo acotado . [24]

Notas

  1. ^ Courcelle, Engelfriet y Rozenberg (1993).
  2. ^ Courcelle (1993).
  3. ^ Courcelle y Olariu (2000).
  4. ^ Golumbic y Rotics (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 y Rotics (2005), fortalecimiento de Courcelle y Olariu (2000), Teorema 5.5.
  11. ^ por Gurski y Wanke (2000).
  12. ^ Oum y Seymour (2006).
  13. ^ Todinca (2003).
  14. ^ Gurski y Wanke (2009).
  15. ^ Cogis y Thierry (2005).
  16. ^ de Courcelle, Makowsky y Rotics (2000).
  17. ^ Fomin y otros (2010).
  18. ^ Dvořák y Král' (2012).
  19. ^ Corneil y otros (2012).
  20. ^ desde Fellows y otros (2009).
  21. ^ Oum y Seymour (2006); Hliněný y Oum (2008); Oum (2008); Fomín y Korhonen (2022).
  22. ^ Fomin y Korhonen (2022).
  23. ^ Gurski y Wanke (2007).
  24. ^ Bonnet y otros (2022).

Referencias