Haga clic en Ancho

En la teoría de grafos, el ancho de camarilla de un gráfico  es un parámetro que describe la complejidad estructural de un gráfico. El parámetro está estrechamente relacionado con el ancho del árbol , pero a diferencia del ancho del árbol, el ancho de la camarilla se puede limitar incluso para gráficos densos . El ancho de clic se define como la cantidad mínima de etiquetas requeridas para construir con las siguientes 4 operaciones

  1. Creando un nuevo vértice v con la etiqueta i ( operación i(v) )
  2. Unión desconectada de dos gráficas rotuladas G y H (operación )
  3. Una conexión de borde de cada vértice con etiqueta i con cada vértice con etiqueta j (operación η(i, j) ), donde
  4. Cambiar el nombre de la etiqueta i a j (operación ρ ( i , j ))

Los gráficos de ancho de camarilla acotados incluyen cographs y gráficos heredados por distancia . Aunque calcular el ancho de la camarilla es NP-difícil , dado que se desconoce el límite superior y no se sabe si se puede calcular en tiempo polinomial cuando se conoce el límite superior, se conocen algoritmos de aproximación eficientes para calcular el ancho de la camarilla. Con base en estos algoritmos y el teorema de Courcelle , muchos problemas de optimización en gráficos que son NP-difíciles para gráficos arbitrarios se pueden resolver o aproximar rápidamente para gráficos con ancho de camarilla limitado.

Las secuencias de construcción en las que se basa la noción de ancho de camarilla fueron formuladas por Courcelle, Engelfried y Rosenberg en 1990 [1] y por Vanke [2] . Khlebikov [3] utilizó el nombre "ancho de clic" para otro concepto . Desde 1993, el término se ha utilizado en su sentido moderno [4] .

Clases especiales de grafos

Los cographs  son exactamente gráficos con ancho de camarilla como máximo dos [5] . Cualquier gráfico heredado por la distancia tiene un ancho de camarilla que no excede 3. Sin embargo, el ancho de camarilla de los gráficos de intervalo no está limitado (según la estructura de la red) [6] . De manera similar, el ancho de la camarilla de los gráficos de permutación bipartitos no está limitado (de acuerdo con la estructura de celosía similar) [7] . Sobre la base de la descripción de los cografos como gráficos sin subgrafos generados isomorfos a caminos sin cuerdas, se clasificó el ancho de camarilla de muchas clases de gráficos definidos por subgrafos generados prohibidos [8] [9] .

Otros gráficos con ancho de clique acotado son k - potencias de hoja para valores acotados de k , es decir, subgrafos generados de hojas del árbol T al grado del gráfico T k . Sin embargo, el grado de hojas con un exponente ilimitado no tiene un ancho de hoja limitado [10] [11] .

Bordes

Courcelle y Olariu [5] , así como Corneil y Rotix [12] , dieron los siguientes límites en el ancho de la camarilla de algunos gráficos:

Además, si el gráfico G tiene un ancho de camarilla k , entonces el grado del gráfico G c tiene un ancho de camarilla que no excede 2 kc k [18] . Aunque hay una exponencial en las desigualdades de ancho de camarilla en comparación con el ancho del árbol y el grado del gráfico, estos límites no dan una superposición: si el gráfico 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 un exponente simple del ancho del árbol [11] .

Complejidad computacional

Problemas no resueltos en Matemáticas : ¿Se puede reconocer un gráfico con 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 se pueden resolver de manera eficiente utilizando programación dinámica en gráficos con ancho de camarilla acotado, si se conoce la secuencia de construcción de estos gráficos [19] [20] . En particular, cualquier gráfico invariante que se pueda expresar en MSO 1 ( lógica de segundo orden de un lugar , un tipo de lógica de segundo orden que permite cuantificadores sobre conjuntos de vértices) tiene un algoritmo de tiempo lineal para ancho acotado gráficos, por una de las formulaciones del teorema de Courcelle [20] . También se pueden encontrar colores óptimos o ciclos hamiltonianos de gráficos de ancho de camarilla acotados en tiempo polinomial si se conoce la secuencia de construcción del gráfico, pero el grado del polinomio aumenta con el ancho de camarilla, y los argumentos de la teoría de la complejidad computacional muestran que tal dependencia parece ser inevitable [21] .

Se pueden reconocer gráficos con ancho de camarilla tres y su secuencia de construcción se puede encontrar en tiempo polinomial usando un algoritmo basado en descomposición dividida [22] . Para clases de gráficos con ancho de camarilla ilimitado, calcular el ancho de camarilla exacto es NP-difícil , y también es NP-difícil obtener una aproximación con error aditivo sublineal [23] . Sin embargo, si se conoce el límite superior del ancho de la camarilla, es posible obtener una secuencia de construcción de gráficos con un ancho acotado (exponencialmente mayor que el ancho real de la camarilla) en tiempo polinomial [17] [24] [25] . Sigue siendo una pregunta abierta si el ancho exacto de la camarilla o la aproximación cercana se pueden calcular en un tiempo fijo paramétricamente resoluble , si se puede calcular en tiempo polinomial para gráficos con cualquier límite de ancho de camarilla fijo, o incluso si los gráficos con ancho de camarilla de ancho cuatro se reconocen en tiempo polinomial [23] .

Enlace al ancho de la madera

La teoría de gráficos de ancho de camarilla acotado tiene similitudes con la teoría de 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 acotado, entonces tiene un ancho de árbol acotado o cualquier gráfico bipartito completo es un subgráfico de algún gráfico en la familia [16] . El ancho del árbol y el ancho de la camarilla también están relacionados por la teoría de gráficos de líneas :  una familia de gráficos tiene un ancho de árbol acotado si y solo si sus gráficos de líneas tienen un ancho de camarilla acotado [26] .

Notas

  1. ↑ Courcelle, Engelfriet, Rozenberg, 1993 .
  2. ↑ Wanke, 1994 .
  3. ↑ Chlebíková, 1992 .
  4. ↑ Courcelle, 1993 .
  5. ↑ 12 Courcelle, Olariu, 2000 .
  6. ↑ Golumbic, Rotics, 2000 .
  7. ↑ Brandstädt, Lozin, 2003 .
  8. ↑ Brandstädt, Dragan, Le, Mosca, 2005 .
  9. ↑ Brandstädt, Engelfriet, Le, Lozin, 2006 .
  10. ↑ Brandstädt, Hundt, 2008 .
  11. ↑ 12 Gurski , Wanke, 2009 .
  12. ↑ Corneil, Rotics, 2005 .
  13. ↑ Courcelle, Olariu, 2000 , p. Corolario 3.3.
  14. ↑ Courcelle, Olariu, 2000 , p. Teorema 4.1.
  15. ↑ Corneil, Rotics, 2005 , Fortalecimiento - Courcelle, Olariu, 2000 , Teorema 5.5.
  16. ↑ 12 Gurski , Wanke, 2000 .
  17. ↑ 12 Oum , Seymour, 2006 .
  18. ↑ Todinaca, 2003 .
  19. ↑ Cogis, Thierry, 2005 .
  20. ↑ 12 Courcelle, Makowsky, Rotics, 2000 .
  21. ↑ Fomin, Golovach, Lokshtanov, Saurabh, 2010 .
  22. ↑ Corneil y colaboradores, 2012 .
  23. ↑ 1 2 Fellows, Rosamond, Rotics, Szeider, 2009 .
  24. ↑ Hliněny, Oum, 2008 .
  25. ↑ Oum, 2009 .
  26. ↑ Gurski, Wanke, 2007 .

Literatura