Número de intersección (teoría de grafos)

En el campo matemático de la teoría de grafos , el número de intersección de un grafo${\displaystyle G=(V,E)}$es el número más pequeño de elementos necesarios para representar${\displaystyle G}$como un grafo de intersección de conjuntos finitos . En dicha representación, cada vértice se representa como un conjunto, y dos vértices están conectados por una arista siempre que sus conjuntos tengan un elemento común. El número de intersección es igual al número más pequeño de camarillas (subgrafos con aristas entre todos los pares de vértices) necesarias para cubrir todas las aristas de${\displaystyle G}$. ^{[ 1 ] [ 2 ]} Tanto este número como el problema computacional de encontrarlo se han estudiado bajo muchos nombres alternativos.

Entre las aplicaciones del número de intersección se incluyen la programación de usuarios de un recurso compartido o de operaciones en ordenadores con instrucciones de palabra muy larga , la asignación de ancho de banda en redes de fibra óptica , la visualización de datos mediante pantallas de letras compactas , el análisis de redes tróficas en biología y la inferencia de complejos proteicos a partir de redes de interacción proteína-proteína .

Cada gráfico con${\displaystyle n}$vértices y${\displaystyle m}$Los bordes tienen un número de intersección como máximo${\displaystyle \min(m,n^{2}/4)}$El número de intersección es NP-difícil de calcular o aproximar, pero tratable con parámetros fijos .

Las dos formulaciones equivalentes del número de intersección, en términos de grafos de intersección o en términos de camarillas que cubren todas las aristas, han sido la fuente de múltiples nombres para este concepto y para el problema computacional de encontrar una representación gráfica de intersección o una cobertura mediante camarillas.

Un conjunto de cliques que cubren todas las aristas de un grafo se denomina cobertura de aristas de clique ^{[ 3 ]} o cobertura de aristas de clique ^{[ 4 ]} , o incluso simplemente cobertura de clique , aunque este último término es ambiguo: una cobertura de clique también puede ser un conjunto de cliques que cubren todos los vértices de un grafo ^{[ 5 ]} . A veces se utiliza "cubrir" en lugar de "cubrir" ^{[ 6 ]} . Además de llamarse número de intersección, el número mínimo de estas cliques se ha denominado contenido R ^{[ 7 ]} , número de cobertura de aristas de clique ^{[ 4 ]} o número de cobertura de clique ^{[ 8 ]} .

El problema de calcular el número de intersección se ha denominado problema del número de intersección , ^{[ 9 ]} problema de la base del grafo de intersección , ^{[ 10 ]} cobertura por camarillas , ^{[ 10 ]} problema de cobertura de camarillas de aristas , [ ^{9 ] y} (debido a una de sus primeras aplicaciones) problema del conflicto de palabras clave . ^{[ 2 ]}

La representación de un grafo como un grafo de intersección abstracto de conjuntos puede utilizarse para construir representaciones de intersección geométricas más concretas del mismo grafo. En particular, si un grafo tiene intersección número${\displaystyle k}$, se puede representar como un grafo de intersección de${\displaystyle k}$Hiperesferas unitarias de dimensión . La dimensión mínima de las hiperesferas en dicha representación se denomina esfericidad de un grafo, por lo que la esfericidad es menor o igual que el número de intersecciones. ^{[ 4 ]}

Una cubierta de clique puede utilizarse como un esquema de etiquetado de adyacencia para un grafo, en el que cada vértice se etiqueta con un valor binario, de forma que se pueda comprobar rápidamente la existencia de una arista entre dos vértices comparando sus valores. Estas etiquetas tienen un bit por clique, que se establece en cero si el vértice no pertenece al clique y en uno si pertenece. Con este esquema de etiquetado, dos vértices son adyacentes si y solo si el bit AND de sus etiquetas es distinto de cero. La longitud de las etiquetas es el número de intersección del grafo. Cuando esta longitud es pequeña, una representación computacional del grafo que utiliza solo estas etiquetas puede consumir menos memoria que métodos explícitos como las listas de adyacencia , y realizar comprobaciones más rápidas para determinar si dos vértices son adyacentes. Este método fue utilizado en una aplicación temprana de los números de intersección, para etiquetar un conjunto de palabras clave de modo que se pudieran detectar rápidamente las palabras clave conflictivas, por E. Kellerman de IBM . Por esta razón, otro nombre para el problema del cálculo de los números de intersección es el problema del conflicto de palabras clave . ^{[ 13 ] [ 14 ]} De manera similar, en geometría computacional , las representaciones basadas en el número de intersección se han considerado como una representación compacta para grafos de visibilidad , aunque existen entradas geométricas para las cuales esta representación requiere un número de cliques casi cuadrático. ^{[ 15 ]}

Otro tipo de aplicaciones proviene de problemas de planificación en los que se debe programar a múltiples usuarios de un recurso compartido para intervalos de tiempo, de manera que las solicitudes incompatibles nunca se programen para el mismo intervalo, pero a todos los pares de solicitudes compatibles se les asigne al menos un intervalo de tiempo juntos. El número de intersección de un grafo de compatibilidades proporciona el número mínimo de intervalos de tiempo necesarios para dicha planificación: un intervalo por cada clique en una cobertura de clique del grafo de compatibilidad. ^{[ 2 ]} En el diseño de compiladores para computadoras con instrucciones de palabra muy larga , surge un problema de planificación diferente: estas computadoras pueden realizar múltiples operaciones en una sola instrucción, por lo que el compilador debe agrupar las operaciones que deben realizarse en la menor cantidad de instrucciones posible, asegurándose de que cada grupo conste de operaciones que la arquitectura de la computadora permita combinar. Se puede utilizar una pequeña cobertura de clique de un grafo de operaciones incompatibles para representar sus incompatibilidades mediante un pequeño número de recursos artificiales (un recurso por clique), lo que permite utilizar técnicas de planificación basadas en recursos para asignar operaciones a instrucciones. ^{[ 16 ]}

FB Shephard y A. Vetta, investigadores de Bell Labs y la Universidad McGill , observan que el número de intersecciones de una red es igual al número mínimo de restricciones necesarias en una formulación de programación entera del problema de calcular conjuntos independientes máximos . En estas formulaciones, se tiene una variable por vértice que puede tomar cualquiera de los dos valores 0 o 1, y una restricción que establece que en cada clique de un clique, las variables suman como máximo uno. Argumentan que, para los grafos de intersección de rutas en ciertas redes de comunicaciones de fibra óptica , estos números de intersecciones son pequeños, lo que explica la relativa facilidad de resolver ciertos problemas de optimización en la asignación de ancho de banda en las redes. ^{[ 3 ]}

En estadística y visualización de datos , las cubiertas de cliques de aristas de un grafo que representa pares de variables estadísticamente indistinguibles se utilizan para producir representaciones de letras compactas que ayudan a visualizar múltiples comparaciones por pares. Estas representaciones se forman eligiendo una letra u otro marcador visual para cada clique y luego etiquetando cada variable con las letras de los cliques a los que pertenece. Este método proporciona una representación gráfica de qué variables son indistinguibles: son indistinguibles si comparten al menos una letra en sus etiquetas. ^{[ 17 ] [ 18 ]}

En el análisis de redes tróficas que describen las relaciones depredador-presa entre especies animales, un grafo de competencia o grafo de superposición de nichos es un grafo no dirigido en el que los vértices representan especies y las aristas representan pares de especies que compiten por la misma presa. Estos se pueden derivar de un grafo acíclico dirigido que representa las relaciones depredador-presa dibujando una arista.${\displaystyle uv}$en el gráfico de competencia siempre que exista una especie presa${\displaystyle w}$de tal manera que el grafo de relación depredador-presa tenga aristas${\displaystyle u\to w}$y${\displaystyle v\to w}$Cada grafo de competencia debe tener al menos un vértice aislado , y el número de competencia de un grafo arbitrario representa el número más pequeño de vértices aislados que se podrían agregar para convertirlo en un grafo de competencia. Biológicamente, si se observa parte de un grafo de competencia, entonces el número de competencia representa el número más pequeño posible de especies presa no observadas necesarias para explicarlo. El número de competencia es como máximo igual al número de intersección: se puede transformar un grafo no dirigido en un grafo de competencia agregando una especie presa por cada clique en una cobertura de clique de aristas. Sin embargo, esta relación no es exacta, porque también es posible que la especie depredadora sea presa de otras especies. En un grafo con${\displaystyle n}$vértices, como máximo${\displaystyle n-2}$Algunos de ellos pueden ser presa de más de una especie, por lo que el número de competencia es al menos el número de intersección menos${\displaystyle n-2}$. ^{[ 19 ]}

Las cubiertas de cliques de aristas también se han utilizado para inferir la existencia de complejos proteicos , sistemas de proteínas que interactúan entre sí, a partir de redes de interacción proteína-proteína que describen únicamente las interacciones por pares entre proteínas. ^{[ 20 ]} De manera más general, Guillaume y Latapy han argumentado que, para redes complejas de todo tipo, reemplazar la red por un grafo bipartito que conecta sus vértices con los cliques en una cubierta de clique resalta la estructura en la red. ^{[ 21 ]}

Cada gráfico con${\displaystyle m}$Los bordes tienen un número de intersección como máximo${\displaystyle m}$Esto se deduce de la observación de que cada arista es en sí misma una camarilla de dos vértices. Hay${\displaystyle m}$de estas camarillas, y juntas cubren todos los bordes, de modo que forman una cubierta de camarilla de borde de tamaño${\displaystyle m}$. ^{[ 22 ]}

También es cierto que cada gráfico con${\displaystyle n}$vértices tiene un número de intersección como máximo${\displaystyle \lfloor n^{2}/4\rfloor }$. Más fuertemente, los bordes de cada${\displaystyle n}$El grafo de vértices puede ser cubierto por como máximo${\displaystyle \lfloor n^{2}/4\rfloor }$camarillas, todas ellas formadas por aristas simples o triángulos. Un algoritmo voraz puede encontrar esta cobertura eliminando dos vértices adyacentes y cubriendo inductivamente el grafo restante. Tras restaurar los dos vértices eliminados, el algoritmo incluye en la cobertura cada triángulo al que ambos pertenecen, lo que cubre cualquier arista que los conecte con vecinos comunes. Cualquier arista restante que conecte uno de los dos vértices eliminados con un vecino, sin formar un triángulo, está cubierta por camarillas de dos vértices. Si no hubiera triángulos que involucraran a los dos vértices eliminados, la arista entre ellos también está cubierta por una camarilla de dos vértices. Por la hipótesis de inducción, la cobertura del grafo con los dos vértices eliminados tiene como máximo${\displaystyle \lfloor (n-2)^{2}/4\rfloor }$camarillas. Los dos vértices eliminados contribuyen como máximo con otro${\displaystyle n-1}$camarillas, maximizadas cuando todos los demás vértices son vecinos no compartidos y la arista entre los dos vértices debe usarse como una camarilla. Sumando estas dos cantidades se obtiene${\displaystyle \lfloor n^{2}/4\rfloor }$camarillas en total. ^{[ 2 ] [ 12 ]} Esto generaliza el teorema de Mantel de que un grafo libre de triángulos tiene como máximo${\displaystyle \lfloor n^{2}/4\rfloor }$bordes, porque en un grafo sin triángulos la única cobertura óptima de bordes de clique tiene un clique por borde y, por lo tanto, el número de intersecciones es igual al número de bordes. ^{[ 2 ]}

Es posible obtener una cota aún más ajustada cuando el número de aristas es estrictamente mayor que${\displaystyle {\tfrac {n^{2}}{4}}}$. Dejar${\displaystyle p}$sea ​​el número de pares de vértices que no están conectados por una arista en el grafo dado${\displaystyle G}$y dejar${\displaystyle t}$sea ​​el único entero para el cual${\displaystyle (t-1)t\leq p<t(t+1)}$. Entonces el número de intersección de${\displaystyle G}$es como máximo${\displaystyle p+t}$. ^{[ 2 ] [ 23 ]} Los grafos que son el complemento de un grafo disperso tienen números de intersección pequeños: el número de intersección de cualquier${\displaystyle n}$-grafo de vértices${\displaystyle G}$es como máximo${\displaystyle 2e^{2}(d+1)^{2}\ln n}$, dónde${\displaystyle e}$es la base del logaritmo natural y${\displaystyle d}$es el grado máximo del gráfico del complemento de${\displaystyle G}$. ^{[ 6 ]}

De los resultados sobre la estructura de los grafos libres de garras se deduce que, cuando un grafo conectado${\displaystyle n}$-un grafo libre de garras de vértice tiene al menos tres vértices independientes, tiene un número de intersección como máximo${\displaystyle n}$Sigue siendo un problema sin resolver si esto es cierto para todos los grafos sin garras sin requerir que tengan grandes conjuntos independientes. ^{[ 8 ]} Una subclase importante de los grafos sin garras son los grafos de línea , grafos que representan aristas y pares de aristas que se tocan de algún otro grafo${\displaystyle G}$. Una cobertura de clique óptima del gráfico de líneas${\displaystyle L(G)}$puede formarse con una camarilla para cada triángulo en${\displaystyle G}$que tiene dos o tres vértices de grado 2, y una camarilla por cada vértice que tiene grado al menos dos y no es un vértice de grado dos de uno de estos triángulos. El número de intersección es el número de camarillas de estos dos tipos. ^{[ 7 ]}

En el modelo de gráficos aleatorios de Erdős-Rényi-Gilbert , en el que todos los gráficos de${\displaystyle n}$Los vértices etiquetados tienen la misma probabilidad (o, equivalentemente, cada arista está presente o ausente, independientemente de otras aristas, con probabilidad${\displaystyle {\tfrac {1}{2}}}$), el número de intersección de un${\displaystyle n}$-el grafo aleatorio de vértices tiene una alta probabilidad dentro de un factor constante de$${\displaystyle {\frac {n^{2}}{\log ^{2}n}},}$$menor por un factor de${\displaystyle \log ^{2}n}$que el número de aristas. En estos grafos, las camarillas máximas tienen (con alta probabilidad) solo un número logarítmico de vértices, lo que implica que se necesitan esta cantidad de ellas para cubrir todas las aristas. La otra dirección de la cota implica demostrar que es posible encontrar suficientes camarillas de tamaño logarítmico para cubrir la mayoría de las aristas, permitiendo que las aristas restantes sean cubiertas por camarillas de dos vértices. ^{[ 24 ] [ 25 ]}

Gran parte de la investigación inicial sobre números de intersección implicó calcular estos números en varios grafos específicos, como los grafos formados al eliminar un subgrafo completo o un emparejamiento perfecto de un grafo completo más grande. ^{[ 26 ]}

Probar si un gráfico dado${\displaystyle G}$tiene un número de intersección como máximo un número dado${\displaystyle k}$es NP-completo . ^{[ 10 ] [ 7 ] [ 14 ]} Por lo tanto, también es NP-difícil calcular el número de intersección de un grafo dado. A su vez, la dificultad del número de intersección se ha utilizado para demostrar que es NP-completo reconocer los cuadrados de grafos divididos . ^{[ 27 ]}

El problema de calcular el número de intersección es, sin embargo, tratable con parámetros fijos : es decir, se puede resolver en un tiempo limitado por un polinomio en${\displaystyle n}$multiplicado por una función mayor pero computable del número de intersección${\displaystyle k}$. ^{[ 5 ] [ 28 ]} Esto se puede demostrar observando que hay como máximo${\displaystyle 2^{k}}$Vecindarios cerrados distintos en el grafo —dos vértices que pertenecen al mismo conjunto de camarillas tienen el mismo vecindario— y que el grafo formado al seleccionar un vértice por vecindario cerrado tiene el mismo número de intersecciones que el grafo original. ^{[ 5 ] [ 29 ]} Por lo tanto, en tiempo polinomial la entrada se puede reducir a un núcleo más pequeño con como máximo${\textstyle 2^{k}}$vértices. Aplicando una búsqueda por fuerza bruta sobre como máximo${\displaystyle 2^{k}!}$La asignación de conjuntos distintos de camarillas a los vértices restantes da como resultado un tiempo doblemente exponencial .${\displaystyle k}$. ^{[ 5 ] [ 28 ]} La dependencia doble exponencial en${\displaystyle k}$no se puede reducir a una exponencial simple mediante una kernelización de tamaño polinomial, a menos que la jerarquía polinomial colapse, ^{[ 30 ]} y si la hipótesis del tiempo exponencial es verdadera, entonces la dependencia doble exponencial es necesaria independientemente de si se usa la kernelización. ^{[ 28 ]} En grafos de ancho de árbol acotado , la programación dinámica en una descomposición en árbol del grafo puede encontrar el número de intersección en tiempo lineal, ^{[ 31 ] [ 20 ]} pero los algoritmos más simples basados ​​en conjuntos finitos de reglas de reducción no funcionan. ^{[ 31 ]}

Existe una constante${\displaystyle c>0}$de tal manera que el problema no se puede aproximar en tiempo polinomial con una razón de aproximación mejor que${\displaystyle n^{c}}$. ^{[ 32 ]} La mejor razón de aproximación que se ha encontrado es mejor que la trivial${\displaystyle O(n^{2})}$por solo un factor polilogarítmico . ^{[ 5 ]} Los investigadores en esta área también han investigado la eficiencia computacional de las heurísticas , sin garantías sobre la calidad de la solución que producen, y su comportamiento en redes del mundo real. ^{[ 5 ] [ 33 ]}

Se conocen algoritmos más eficientes para ciertas clases especiales de grafos. El número de intersección de un grafo de intervalos siempre es igual a su número de cliques maximales , que se puede calcular en tiempo polinomial. ^{[ 34 ] [ 35 ]} De manera más general, en grafos cordales , el número de intersección se puede calcular mediante un algoritmo que considera los vértices en un ordenamiento de eliminación del grafo (un ordenamiento en el que cada vértice y sus vecinos posteriores forman un clique) y que, para cada vértice${\displaystyle v}$, forma una camarilla para${\displaystyle v}$y sus vecinos posteriores siempre que al menos uno de los bordes incidentes a${\displaystyle v}$no está cubierto por ningún clique anterior. ^{[ 35 ]} También es posible encontrar el número de intersección en tiempo lineal en grafos de arcos circulares . ^{[ 36 ]} Sin embargo, aunque estos grafos solo tienen un número polinomial de cliques para elegir para la cobertura, tener pocos cliques por sí solo no es suficiente para hacer el problema fácil: existen familias de grafos con un número polinomial de cliques para los cuales el número de intersección sigue siendo NP-difícil. ^{[ 9 ]} El número de intersección también se puede encontrar en tiempo polinomial para grafos cuyo grado máximo es cinco, pero es NP-difícil para grafos de grado máximo seis. ^{[ 37 ] [ 38 ]} En grafos planares , calcular el número de intersección exactamente sigue siendo NP-difícil, pero tiene un esquema de aproximación en tiempo polinomial basado en la técnica de Baker . ^{[ 20 ]}

• Dimensión bipartita , el número mínimo de bicliques necesarios para cubrir todas las aristas de un grafo.
• Grafo acotado , un tipo de grafo caracterizado por cubiertas de aristas de clique de una forma especial.

• Weisstein, Eric W. , "Número de intersección" , MathWorld{{cite web}}: Mantenimiento de CS1: configuración sobrescrita ( enlace )