Subgrafo denso

En teoría de grafos e informática , un subgrafo denso es un subgrafo con muchas aristas por vértice. Esto se formaliza de la siguiente manera: sea G = ( V , E ) un grafo no dirigido y sea S = ( V ∩ _S , ES ) un subgrafo de G. Entonces _, la densidad de S se define como:

${\displaystyle d(S)={|E_{S}| \over |V_{S}|}}$

La densidad del subgrafo de máxima densidad de un grafo se denomina a veces densidad de subgrafo . Un subgrafo con densidad máxima también puede considerarse como un subgrafo con el grado promedio máximo en el grafo.

La densidad de subgrafos es asintótica a la noción relacionada de arboricidad y a la degeneración de grafos .

El problema del subgrafo más denso es el de encontrar un subgrafo de máxima densidad. En 1984, Andrew V. Goldberg desarrolló un algoritmo de tiempo polinomial para encontrar el subgrafo de máxima densidad utilizando una técnica de flujo máximo . Este algoritmo fue mejorado por Gallo, Grigoriadis y Tarjan en 1989 ^{[ 1 ]} para ejecutarse en tiempo O ( nm log( n² ^/ m )) . Charikar presentó en 2000 un problema de programación lineal simple para encontrar la solución óptima . ^{[ 2 ]}

Muchos de los algoritmos exactos para resolver el problema del subgrafo más denso son poco prácticos con datos del mundo real, ^{[ 3 ]} lo que ha llevado al estudio de algoritmos de aproximación para el problema del subgrafo más denso. Un ejemplo sencillo${\textstyle {\frac {1}{2}}}$Charikar dio una aproximación para encontrar el subgrafo más denso en 2000, basada en un procedimiento de pelado que fue propuesto por primera vez por Asahiro, Iwama, Tamaki y Tokuyama en 1996 como un algoritmo de aproximación para el subgrafo más denso.${\displaystyle k}$Problema del subgrafo. ^{[ 4 ]} En este algoritmo, el vértice con el grado más bajo se elimina repetidamente, creando un ordenamiento de vértices.${\displaystyle v_{1},v_{2},\dots,v_{n}}$, dónde${\displaystyle v_{i}}$es el${\displaystyle i}$vértice -ésimo del grafo que se va a eliminar. El subgrafo devuelto por el algoritmo es el grafo inducido por el conjunto${\displaystyle S_{i}=\{v_{i},v_{i+1},\dots,v_{n}\}}$con la mayor densidad. Al usar el dual del LP para el algoritmo exacto que proporcionó, Charikar demostró que este procedimiento se ejecuta en tiempo lineal y produce un subgrafo con al menos el 50% de la densidad óptima. ^{[ 2 ]} Aunque el 50% es una cota ajustada, en la práctica, este procedimiento de pelado voraz produce alrededor del 80% de la densidad óptima en grafos del mundo real. ^{[ 3 ]}

En 2020, Boob et al. presentaron un algoritmo de pelado iterativo que busca acercarse al subgrafo óptimo repitiendo el procedimiento de pelado varias veces. ^{[ 3 ]} En lugar de eliminar los vértices en función de su grado actual, se asigna una carga a cada vértice en función de los datos de iteraciones anteriores, y los vértices se pelan en función de sus cargas. En 2022, Chekuri, Quanrud y Torres demostraron que este procedimiento converge a un${\displaystyle (1-\epsilon )}$aproximación para el problema del subgrafo más denso después${\textstyle O({\frac {\Delta \log n}{\lambda ^{*}\epsilon ^{2}}})}$iteraciones del algoritmo, donde${\textstyle \lambda ^{*}}$es la densidad óptima y${\displaystyle \Delta }$es el grado máximo en el grafo. ^{[ 5 ]} También demostraron que se podría utilizar un algoritmo similar para encontrar hipergrafos más densos .

Existen muchas variaciones del problema del subgrafo más denso. Una de ellas es el problema del subgrafo k más denso , donde el objetivo es encontrar el subgrafo de máxima densidad con exactamente k vértices. Este problema generaliza el problema de la camarilla y, por lo tanto, es NP-difícil en grafos generales. Existe un algoritmo polinomial que aproxima el subgrafo k más denso dentro de una razón de${\displaystyle n^{1/4\,+\,\epsilon }}$por cada${\displaystyle \epsilon >0}$, ^{[ 6 ]} mientras que no admite una${\displaystyle n^{1/\!\operatorname {polyloglog} n}}$-aproximación en tiempo polinomial a menos que la hipótesis del tiempo exponencial sea falsa. ^{[ 7 ]} Bajo una suposición más débil que${\displaystyle {\mathsf {NP}}\nsubseteq \bigcap _{\epsilon >0}{\mathsf {BPTIME}}(2^{n^{\epsilon }})}$, no existe PTAS para el problema. ^{[ 8 ]}

El problema sigue siendo NP-difícil en grafos bipartitos y grafos cordales , pero es polinomial para árboles y grafos divididos . ^{[ 9 ]} Queda por dilucidar si el problema es NP-difícil o polinomial en grafos de intervalos (propios) y grafos planares ; sin embargo, una variación del problema en la que se requiere que el subgrafo sea conexo es NP-difícil en grafos planares. ^{[ 10 ]}

El objetivo del más denso en la mayoría de los casos${\displaystyle k}$El problema consiste en encontrar el subgrafo de máxima densidad en como máximo${\displaystyle k}$vértices. Andersen y Chellapilla demostraron que si existe un${\displaystyle \alpha }$-aproximación para este problema entonces eso conducirá a una${\displaystyle \Theta (\alpha ^{2})}$-aproximación para el más denso${\displaystyle k}$problema del subgrafo. ^{[ 11 ]} Posteriormente, Khuller y Saha mejoraron esto demostrando que un${\displaystyle \alpha }$-aproximación para el más denso en la mayoría${\displaystyle k}$El subgrafo implica un${\displaystyle 4\alpha }$-aproximación para el más denso${\displaystyle k}$Problema del subgrafo. ^{[ 12 ]}

Al menos el más denso${\displaystyle k}$El problema se define de forma similar al más denso en la mayoría de los casos.${\displaystyle k}$Problema de subgrafos. El problema es NP-completo, ^{[ 12 ]} pero admite una 2-aproximación en tiempo polinomial. ^{[ 13 ]} Además, hay cierta evidencia de que este algoritmo de aproximación es esencialmente el mejor posible: asumiendo la hipótesis de expansión de conjuntos pequeños (una suposición de complejidad computacional estrechamente relacionada con la conjetura de juegos únicos ), entonces es NP-difícil aproximar el problema a dentro de${\displaystyle (2-\epsilon )}$factor para cada constante${\displaystyle \epsilon >0}$. ^{[ 14 ]}

Charalampos Tsourakakis presentó el${\displaystyle k}$Problema del subgrafo más denso -clique. Esta variación del problema del subgrafo más denso tiene como objetivo maximizar el número promedio de subgrafos inducidos.${\displaystyle k}$camarillas${\displaystyle d_{k}(S)={|C_{k}(S)| \over |V_{S}|}}$, dónde${\displaystyle C_{k}(S)}$es el conjunto de${\displaystyle k}$-cliques inducidos por${\displaystyle S}$. Nótese que el problema del subgrafo más denso se obtiene como un caso especial para${\displaystyle k=2}$Esta generalización proporciona un enfoque politemporal empíricamente exitoso para extraer grandes grupos cercanos a partir de redes reales a gran escala.

Qin et al. introdujeron el problema del descubrimiento de los k subgrafos localmente más densos en un grafo, cada uno de los cuales alcanza la mayor densidad en su región local en el grafo: no está contenido en ningún supergrafo con la misma o mayor densidad, ni contiene subgrafos con una densidad que esté débilmente conectada con el resto del subgrafo local más denso. Nótese que el problema del subgrafo más denso se obtiene como un caso especial para${\displaystyle k=1}$El conjunto de subgrafos localmente más densos en un grafo se puede calcular en tiempo polinomial.