El recuento de intersecciones de un gráfico es el número más pequeño de elementos en la representación de un gráfico dado como un gráfico de intersección de conjunto finito , o de manera equivalente, el número más pequeño de clicas necesarias para cubrir todos los bordes del gráfico [1] [2] [ 3] .
Sea F una familia de conjuntos (se permite repetir conjuntos en F ). Entonces, el gráfico de intersección F es un gráfico no dirigido que tiene un vértice para cada miembro de F y una arista entre dos conjuntos que tienen una intersección no vacía. Cualquier gráfico se puede representar como un gráfico de intersección [4] . El número de intersección de un grafo es el menor número k tal que existe una representación de tipo para la cual la unión de conjuntos F tiene k elementos [1] . El problema de encontrar una representación en forma de grafo de intersección con un número dado de elementos se conoce como problema de encontrar la base del grafo de intersección [5] .
Una definición alternativa del número de intersección de un gráfico G es el número más pequeño de camarillas en G ( subgrafos completos de G ) que cubren todos los bordes de G [1] [6] . Un conjunto de camarillas con esta propiedad se denomina cobertura de camarilla de borde y, por lo tanto, el número de intersecciones a veces se denomina número de cobertura de camarilla de borde [7] .
La igualdad del número de intersecciones y el número de bordes cubiertos por camarillas se demuestra "simple". En una dirección, supongamos que G es el grafo de intersección de una familia F de conjuntos cuya unión U tiene k elementos. Entonces, para cualquier elemento x de U , el subconjunto de vértices del gráfico G correspondiente a los conjuntos que contienen x forman una camarilla: dos vértices cualesquiera de este subconjunto son adyacentes, ya que sus conjuntos correspondientes tienen una intersección no vacía que contiene x . Además, cualquier arista en G está contenida en una de estas clicas, ya que una arista corresponde a una intersección no vacía , y una intersección no es vacía si contiene al menos un elemento U. Así, las aristas de G pueden estar cubiertas por k camarillas, una para cada elemento de U. En la otra dirección, si el grafo G puede ser cubierto por k cliques, entonces cada vértice del grafo G puede ser representado por un conjunto de cliques que contienen el vértice [8] .
Obviamente, un gráfico con m aristas tiene un número de intersecciones que no excede m - cualquier arista forma una camarilla, y estas camarillas juntas cubren todas las aristas [9] .
También es cierto que cualquier gráfico con n vértices tiene como máximo n 2/4 intersecciones . Más estrictamente, las aristas de cualquier gráfico con n vértices se pueden dividir como máximo en n 2/4 camarillas, que son aristas simples o triángulos [2] [ 8] . Esto generaliza el teorema de Mantel que establece que un gráfico sin triángulos tiene como máximo n 2/4 aristas . Para gráficos sin triángulos, la cobertura de clique de borde óptima tiene un clique para cada borde y, por lo tanto, el número de intersecciones es igual al número de bordes [2] .
Una restricción aún más fuerte es posible si el número de aristas es estrictamente mayor que n 2/4 . Sea p el número de pares de vértices no conectados por aristas en el gráfico G dado , y sea t el número para el cual t ( t − 1) ≤ p < t ( t + 1) . Entonces el número de intersecciones del gráfico G no excede p + t [2] [10] .
Los gráficos que son complementos de gráficos dispersos tienen un pequeño número de intersecciones: el número de intersecciones de cualquier gráfico G con n vértices i no excede 2 e 2 ( d + 1) 2 ln n , donde e es la base del logaritmo natural de , d es el grado máximo del grafo complementario G [11 ] .
Verificar que para un grafo G dado el número de intersecciones no exceda un número k dado es un problema NP-completo [12] [13] [14] . Por lo tanto, es un problema NP-difícil calcular el número de intersección de un gráfico dado.
El problema de calcular el número de intersecciones, sin embargo, tiene una solución paramétrica fija . Es decir, existe una función f tal que cuando el número de intersecciones es igual al número k , el tiempo para calcular este número no excede el producto de f ( k ) por un polinomio en n . Esto se puede mostrar observando que hay como máximo 2k vecindarios cerrados distintos en el gráfico. Dos vértices que pertenecen al mismo conjunto de camarillas tienen los mismos vecinos, y luego el grafo formado al elegir un vértice para cada vecindad cerrada tiene el mismo número de intersecciones que el grafo original. Por lo tanto, en tiempo polinomial, la entrada se puede reducir a un núcleo más pequeño con un máximo de 2k vértices. La aplicación del algoritmo de retroceso con tiempo de ejecución exponencial para este kernel da como resultado una función f que es el doble exponente de k [15] . La doble dependencia exponencial de k no puede reducirse a una simple dependencia exponencial extrayendo un kernel de tamaño polinomial hasta que la jerarquía polinómica desaparezca [16] , y si la hipótesis del tiempo exponencial es correcta, la doble dependencia exponencial no puede evitarse si usamos kernel extracción o no [ 17] .
Se conocen algoritmos más eficientes para ciertas clases especiales de gráficos. El número de intersecciones de un gráfico de intervalo siempre es igual al número de cliques máximos del gráfico, que se puede calcular en tiempo polinomial [18] [19] . De manera más general, el número de intersecciones de gráficos cordales se puede calcular mediante un algoritmo que construye el orden en el que se excluyen los vértices del gráfico. En cada paso, para cada vértice v , formamos una camarilla para el vértice v y sus vecinos y excluimos el vértice si hay bordes que son incidentes con v pero aún no están cubiertos por camarillas [19] .