Ancho de la camarilla

En teoría de grafos , el ancho de clique 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, 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 grafos etiquetados G y H (denotados por${\displaystyle G\oplus H}$)
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 (denotado por ρ ( i , j ) )

Los grafos con ancho de clique acotado incluyen los cografos y los grafos hereditarios de distancia . Si bien calcular el ancho de clique cuando no está acotado es un problema NP-difícil , y se desconoce si se puede calcular en tiempo polinomial cuando está acotado, se conocen algoritmos de aproximación eficientes para el ancho de clique. Basándose en estos algoritmos y en el teorema de Courcelle , muchos problemas de optimización de grafos que son NP-difíciles para grafos arbitrarios pueden resolverse o aproximarse rápidamente en grafos con ancho de clique acotado.

Las secuencias de construcción subyacentes al concepto de ancho de clique fueron formuladas por Courcelle , Engelfriet y Rozenberg en 1990 ^{[ 1 ]} y por Wanke (1994) . El nombre "ancho de clique" fue utilizado para un concepto diferente por Chlebíková (1992) . Para 1993, el término ya tenía su significado actual. ^{[ 2 ]}

Los cografos son precisamente los grafos con ancho de clique como máximo 2. ^{[ 3 ]} Todo grafo hereditario de distancia tiene un ancho de clique como máximo 3. Sin embargo, el ancho de clique de los grafos de intervalo unitario no está acotado (según su estructura de cuadrícula). ^{[ 4 ]} De manera similar, el ancho de clique de los grafos de permutación bipartitos no está acotado (según una estructura de cuadrícula similar). ^{[ 5 ]} Basándose en la caracterización de los cografos como los grafos sin subgrafo inducido isomorfo a un camino con cuatro vértices, se ha clasificado el ancho de clique de muchas clases de grafos definidas por subgrafos inducidos prohibidos. ^{[ 6 ]}

Otros grafos con ancho de clique 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 el grafo potencia T ^k . Sin embargo, las potencias de hojas con exponentes no acotados no tienen ancho de clique acotado. ^{[ 7 ]}

Courcelle y Olariu (2000) y Corneil y Rotics (2005) demostraron las siguientes cotas para el ancho de clique de ciertos grafos:

• Si un grafo tiene un ancho de clique como máximo k , entonces también lo tiene cada subgrafo inducido del grafo. ^{[ 8 ]}
• El grafo complemento de un grafo de ancho de clique k tiene un ancho de clique como máximo 2k . ^{[ 9 ]}
• Los grafos de ancho de árbol w tienen un ancho de clique como máximo 3 · 2 ^{w − 1} . La dependencia exponencial en esta cota es necesaria: existen grafos cuyo ancho de clique es exponencialmente mayor que su ancho de árbol. ^{[ 10 ]} En la otra dirección, los grafos de ancho de clique acotado pueden tener un ancho de árbol no acotado; por ejemplo, los grafos completos de n vértices tienen un ancho de clique de 2 pero un ancho de árbol de n − 1 . Sin embargo, los grafos de ancho de clique k que no tienen un grafo 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 grafos dispersos , tener un ancho de árbol acotado es equivalente a tener un ancho de clique acotado. ^{[ 11 ]}
• Otro parámetro del gráfico, el ancho de rango , está acotado en ambas direcciones por el ancho de clique: ancho de rango ≤ ancho de clique ≤ 2 ^{ancho de rango +} 1. ^{[ 12 ]}

Además, si un grafo G tiene un ancho de clique k , entonces la potencia del grafo G ^c tiene un ancho de clique como máximo 2 kc ^k . ^{[ 13 ]} Aunque hay una brecha exponencial tanto en la cota para el ancho de clique a partir del ancho de árbol como en la cota para el ancho de clique de las potencias de grafos, estas cotas no se acumulan entre sí: si un grafo G tiene un ancho de árbol w , entonces G ^c tiene un ancho de clique como máximo 2( c + 1) ^{w + 1} − 2 , solo exponencial simple en el ancho de árbol. ^{[ 14 ]}

Muchos problemas de optimización que son NP-difíciles para clases de grafos más generales pueden resolverse eficientemente mediante programación dinámica en grafos de ancho de clique acotado, cuando se conoce una secuencia de construcción para estos grafos. ^{[ 15 ] [ 16 ]} En particular, cada propiedad de grafo que puede expresarse en lógica monádica de segundo orden MSO ₁ (una forma de lógica que permite la cuantificación sobre conjuntos de vértices) tiene un algoritmo de tiempo lineal para grafos de ancho de clique 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 clique acotado en tiempo polinomial, cuando se conoce una secuencia de construcción, pero el exponente del polinomio aumenta con el ancho del clique, y la evidencia de la teoría de la complejidad computacional muestra que esta dependencia probablemente sea necesaria. ^{[ 17 ]} Los grafos de ancho de clique acotado son χ- acotados , lo que significa que su número cromático es como máximo una función del tamaño de su clique más grande. ^{[ 18 ]}

Los grafos de ancho de clique tres pueden ser reconocidos, y se puede encontrar una secuencia de construcción para ellos, en tiempo polinomial usando un algoritmo basado en descomposición dividida . ^{[ 19 ]} Para grafos de ancho de clique no acotado, es NP-difícil calcular el ancho de clique exactamente, y también es NP-difícil obtener una aproximación con error aditivo sublineal. ^{[ 20 ]} Sin embargo, cuando el ancho de clique está acotado, es posible obtener una secuencia de construcción de ancho acotado (exponencialmente mayor que el ancho de clique real) en tiempo polinomial, ^{[ 21 ]} en particular en tiempo cuadrático en el número de vértices. ^{[ 22 ]} Queda por determinar si el ancho exacto del clique, o una aproximación más precisa del mismo, puede calcularse en tiempo tratable con parámetros fijos , si puede calcularse en tiempo polinomial para cada límite fijo del ancho del clique, o incluso si los grafos de ancho de clique cuatro pueden reconocerse en tiempo polinomial. ^{[ 20 ]}

La teoría de grafos de ancho de clique acotado se asemeja 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 ancho de clique acotado, entonces o bien tiene ancho de árbol acotado o bien todo grafo bipartito completo es un subgrafo de un grafo de la familia. ^{[ 11 ]} El ancho de árbol y el ancho de clique también están conectados a través de la teoría de grafos de línea : una familia de grafos tiene ancho de árbol acotado si y solo si sus grafos de línea tienen ancho de clique acotado. ^{[ 23 ]}

Los grafos de ancho de clique acotado también tienen ancho de twin acotado . ^{[ 24 ]}