Partición sesgada

Partición oblicua de un grafo cordal . En el lado izquierdo de la partición, las partes superior e inferior están desconectadas entre sí. En el lado derecho de la partición, existen todas las aristas posibles de arriba a abajo, formando un grafo cuyo complemento está desconectado.

En teoría de grafos , una partición oblicua de un grafo es una partición de sus vértices en dos subconjuntos, de modo que el subgrafo inducido formado por uno de los dos subconjuntos está desconectado y el subgrafo inducido formado por el otro subconjunto es el complemento de un grafo desconectado. Las particiones oblicuas desempeñan un papel importante en la teoría de grafos perfectos .

Definición

Una partición oblicua de un grafo es una partición de sus vértices en dos subconjuntos y para los cuales el subgrafo inducido está desconectado y el subgrafo inducido es el complemento de un grafo desconectado (co-desconectado). De manera equivalente, una partición oblicua de un grafo puede describirse mediante una partición de los vértices de en cuatro subconjuntos , , , y , tales que no hay aristas de a y tales que existen todas las aristas posibles de a ; para tal partición, los subgrafos inducidos y están desconectados y co-desconectados respectivamente, por lo que podemos tomar y . ${\displaystyle G}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle G[X]}$ ${\displaystyle G[Y]}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle D}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle D}$ ${\displaystyle G[A\cup B]}$ ${\displaystyle G[C\cup D]}$ ${\displaystyle X=A\cup B}$ ${\displaystyle Y=C\cup D}$

Ejemplos

Todo grafo de trayectoria con cuatro o más vértices tiene una partición oblicua, en la que el conjunto codexconectado es una de las aristas interiores de la trayectoria y el conjunto desconectado consta de los vértices a cada lado de esta arista. Sin embargo, no es posible que un grafo de ciclo de cualquier longitud tenga una partición oblicua: sin importar qué subconjuntos del ciclo se elijan como el conjunto , el conjunto complementario tendrá el mismo número de componentes conectados, por lo que no es posible que esté desconectado y codexconectado. ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$

Si un grafo tiene una partición oblicua, también la tiene su complemento . Por ejemplo, los complementos de los grafos de trayectoria tienen particiones oblicuas y los complementos de los grafos de ciclo no.

Casos especiales

Si un grafo es en sí mismo desconectado, entonces con solo tres excepciones simples (un grafo vacío , un grafo con una arista y tres vértices, o una correspondencia perfecta de cuatro vértices ) tiene una partición oblicua, en la que el lado codesconectado de la partición consiste en los puntos finales de una sola arista y el lado desconectado consiste en todos los demás vértices. Por la misma razón, si el complemento de un grafo es desconectado, entonces con un conjunto correspondiente de tres excepciones debe tener una partición oblicua. ^[1]

Si un grafo tiene un separador de clique (un clique cuya eliminación desconectaría los vértices restantes) con más de un vértice, entonces la partición en el clique y los vértices restantes forma una partición oblicua. Un conjunto de corte de clique con un vértice es un punto de articulación ; si existe tal vértice, entonces con un pequeño número de simples excepciones, hay una partición oblicua en la que el lado codexconectado consiste en este vértice y uno de sus vecinos. ^[1]

Un conjunto de corte en estrella en un grafo es un separador de vértices en el que uno de los vértices separadores es adyacente a todos los demás. Cada separador de clique es un conjunto de corte en estrella. Necesariamente, un grafo con un conjunto de corte en estrella (con más de un vértice) tiene una partición sesgada en la que el subgrafo codexconectado consta de los vértices en el conjunto de corte en estrella y el subgrafo desconectado consta de todos los vértices restantes. ^[1] ${\displaystyle G}$

Un módulo (o conjunto homogéneo) es un subconjunto no trivial de los vértices de tal que, para cada vértice que no está en , o bien es adyacente a todos los vértices en o bien a ninguno de ellos. Si un grafo tiene un módulo y, fuera de él, existen tanto vértices adyacentes a todos los vértices en como otros vértices adyacentes a ninguno de ellos, entonces tiene un conjunto de corte en estrella que consiste en un vértice en el módulo junto con sus vecinos fuera del módulo. Por otro lado, si existe un módulo en el que uno de estos dos subconjuntos está vacío, entonces el grafo está desconectado o co-desconectado y nuevamente (con las tres simples excepciones) tiene un conjunto de corte oblicuo. ^[1] ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle H}$ ${\displaystyle v}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle G}$

Historia

Las particiones oblicuas fueron introducidas por Chvátal (1985), en conexión con los grafos perfectos . Chvátal demostró que un grafo mínimamente imperfecto no podía tener un conjunto de corte en estrella. Trivialmente, los grafos desconectados no pueden ser mínimamente imperfectos, y también se sabía que los grafos con separadores de clique o módulos no podían ser mínimamente imperfectos. ^[2] Claude Berge había conjeturado a principios de la década de 1960 que los grafos perfectos eran lo mismo que los grafos de Berge, grafos sin ciclo impar inducido (de longitud cinco o más) o su complemento, y (debido a que los ciclos y sus complementos no tienen particiones oblicuas) ningún grafo mínimo que no sea de Berge puede tener una partición oblicua. Motivado por estos resultados, Chvátal conjeturó que ningún grafo mínimamente imperfecto podría tener una partición oblicua. Varios autores demostraron casos especiales de esta conjetura, pero permaneció sin resolver durante muchos años. ^[3]

Las particiones oblicuas adquirieron importancia cuando Chudnovsky et al. (2006) las utilizó para demostrar el teorema fuerte de grafos perfectos , según el cual los grafos de Berge son, en efecto, los mismos que los grafos perfectos. Chudnovsky et al. no pudieron demostrar directamente la conjetura de Chvátal, pero en su lugar demostraron un resultado más débil: que un contraejemplo mínimo del teorema (si existiera) no podría tener una partición oblicua equilibrada, una partición oblicua en la que cada camino inducido con puntos finales en un lado de la partición y vértices interiores en el otro lado tiene una longitud par. Este resultado formó un lema clave en su demostración, y la versión completa del lema de Chvátal se desprende de su teorema. ^[4]

En la teoría de grafos estructurales

Las particiones oblicuas forman uno de los componentes clave de una descomposición estructural de grafos perfectos utilizada por Chudnovsky et al. (2006) como parte de su prueba del teorema fuerte del grafo perfecto. Chudnovsky et al. demostraron que cada grafo perfecto pertenece a una de las cinco clases básicas de grafos perfectos, o tiene uno de los cuatro tipos de descomposición en grafos más simples, uno de los cuales es una partición oblicua.

Un ejemplo más simple de una descomposición estructural usando particiones sesgadas es dado por Seymour (2006). Él observa que cada gráfico de comparabilidad es completo , es bipartito o tiene una partición sesgada. Porque, si cada elemento de un conjunto parcialmente ordenado es un elemento mínimo o un elemento máximo, entonces el gráfico de comparabilidad correspondiente es bipartito. Si el ordenamiento es un orden total , entonces el gráfico de comparabilidad correspondiente es completo. Si no se da ninguno de estos dos casos, pero cada elemento que no es mínimo ni máximo es comparable con todos los demás elementos, entonces la partición en los elementos mínimos y no mínimos (si hay más de un elemento mínimo) o la partición en los elementos máximos y no máximos (si hay más de un elemento máximo) forma un conjunto de corte en estrella. Y en el caso restante, existe un elemento del orden parcial que no es mínimo, no máximo y no comparable con todos los demás elementos; en este caso, hay una partición sesgada (el complemento de un corte en estrella) en el que el lado codesconectado consiste en los elementos comparables a (sin incluirse a sí mismo) y el lado desconectado consiste en los elementos restantes. ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$

Los grafos cordales tienen una descomposición aún más simple de un tipo similar: o son completos o tienen un separador de clique. Hayward (1985) demostró, de manera análoga, que todo grafo débilmente cordal conexo y co-conexo (un grafo sin ciclo inducido o su complemento de longitud mayor que cuatro) con cuatro o más vértices tiene un corte en estrella o su complemento, de lo que se sigue por el lema de Chvátal que todo grafo de este tipo es perfecto.

Algoritmos y complejidad

Una partición sesgada de un gráfico dado, si existe, se puede encontrar en tiempo polinomial . Esto fue demostrado originalmente por de Figueiredo et al. (2000) pero con un tiempo de ejecución imprácticamente grande de , donde es el número de vértices en el gráfico de entrada. Kennedy y Reed (2008) mejoraron el tiempo de ejecución a ; aquí es el número de aristas de entrada. ${\displaystyle O(n^{101})}$ ${\displaystyle n}$ ${\displaystyle O(n^{4}m)}$ ${\displaystyle m}$

Es NP-completo probar si un gráfico contiene una partición sesgada en la que una de las partes del lado codesconectado es independiente. ^[5] Probar si un gráfico dado contiene una partición sesgada balanceada también es NP-completo en gráficos arbitrarios, pero se puede resolver en tiempo polinomial en gráficos perfectos. ^[6]

Notas

1. Reed (2008).
2. Reed (2008). La inexistencia de módulos en grafos mínimamente imperfectos fue utilizada por Lovász (1972) en su demostración del teorema del grafo débil perfecto .
3. Véase Cornuéjols y Reed (1993) para el caso en el que el lado codexconectado de la partición es multipartito, y Roussel y Rubio (2001) para el caso en el que una de las dos partes del lado codexconectado es independiente.
4. Seymour (2006).
5. Dantas y otros (2004).
6. Trotignon (2008).

Referencias

• Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2006), "El teorema del grafo perfecto fuerte", Anales de Matemáticas , 164 (1): 51–229, arXiv : math/0212070 , doi :10.4007/annals.2006.164.51.
• Chvátal, V. (1985), "Conjuntos de corte en estrella y grafos perfectos", Journal of Combinatorial Theory , Serie B, 39 (3): 189–199, doi :10.1016/0095-8956(85)90049-8, MR  0815391.
• Cornuéjols, G. ; Reed, B. (1993), "Conjuntos de corte multipartitos completos en gráficos imperfectos mínimos", Journal of Combinatorial Theory , Serie B, 59 (2): 191–198, doi : 10.1006/jctb.1993.1065 , MR  1244930.
• Dantas, Simone; de ​​Figueiredo, Celina MH; Klein, Sulamita; Gravier, Sylvain; Reed, Bruce A. (2004), "Problema de partición sesgada estable", Discrete Applied Mathematics , 143 (1–3): 17–22, doi : 10.1016/j.dam.2004.01.001 , MR  2087864.
• de Figueiredo, Celina MH; Klein, Sulamita; Kohayakawa, Yoshiharu ; Reed, Bruce A. (2000), "Cómo encontrar particiones sesgadas de manera eficiente", Journal of Algorithms , 37 (2): 505–521, doi :10.1006/jagm.1999.1122, MR  1788847.
• Hayward, Ryan B. (1985), "Gráficos débilmente triangulados", Journal of Combinatorial Theory , Serie B, 39 (3): 200–208, doi : 10.1016/0095-8956(85)90050-4 , MR  0815392.
• Kennedy, William S.; Reed, Bruce (2008), "Reconocimiento rápido de particiones torcidas", Computational Geometry and Graph Theory: International Conference, KyotoCGGT 2007, Kyoto, Japón, 11-15 de junio de 2007, Documentos seleccionados revisados , Lecture Notes in Computer Science , vol. 4535, Berlín: Springer, págs. 101-107, doi :10.1007/978-3-540-89550-3_11, MR  2672388.
• Lovász, László (1972), "Hipergrafos normales y la conjetura del grafo perfecto", Discrete Mathematics , 2 (3): 253–267, doi :10.1016/0012-365X(72)90006-4.
• Reed, Bruce (2008), "Particiones sesgadas en grafos perfectos" (PDF) , Discrete Applied Mathematics , 156 (7): 1150–1156, doi : 10.1016/j.dam.2007.05.054 , MR  2404228.
• Roussel, F.; Rubio, P. (2001), "Acerca de las particiones sesgadas en grafos imperfectos mínimos", Journal of Combinatorial Theory , Serie B, 83 (2): 171–190, doi : 10.1006/jctb.2001.2044 , MR  1866394.
• Seymour, Paul (2006), "Cómo se encontró la prueba de la conjetura del grafo perfecto fuerte" (PDF) , Gazette des Mathématiciens (109): 69–83, MR  2245898.
• Trotignon, Nicolas (2008), "Descomposición de grafos de Berge y detección de particiones sesgadas equilibradas" (PDF) , Journal of Combinatorial Theory , Serie B, 98 (1): 173–225, arXiv : 1309.0680 , doi :10.1016/j.jctb.2007.07.004, MR  2368032.