En informática, la noción de subgrafos altamente conectados aparece con frecuencia. Esta noción se puede formalizar de la siguiente manera. Dejarser un grafo no dirigido y dejarser un subgrafo de. Entonces la densidad de se define como .
El problema del subgrafo más denso es el de encontrar un subgrafo de densidad máxima. En 1984, Andrew V. Goldberg desarrolló un algoritmo de tiempo polinomial para encontrar el subgráfico de densidad máxima utilizando una técnica de flujo máximo . Esto ha sido mejorado por Gallo, Grigoriadis y Tarjan en 1989 [1] para que se ejecute enhora. Charikar ofreció en 2000 un PL sencillo para encontrar la solución óptima. [2]
La más densa k subgrafo
Hay muchas variaciones sobre el problema del subgrafo más denso. Uno de ellos es el más denso problema de subgrafo, donde el objetivo es encontrar el subgrafo de densidad maxima exactamente vértices. Este problema generaliza el problema de la camarilla y, por lo tanto, es NP-difícil en los gráficos generales. Existe un algoritmo polinomial que se aproxima al más denso subgrafo dentro de una razn de para cada , [3] aunque no admite-aproximación en tiempo polinomial a menos que la hipótesis del tiempo exponencial sea falsa. [4] Bajo una suposición más débil de que, no existe ningún PTAS para el problema. [5]
El problema sigue siendo NP-hard en gráficos bipartitos y gráficos cordales, pero es polinomial para árboles y gráficos divididos . [6] Está abierto si el problema es NP-duro o polinomial en gráficas de intervalo (adecuadas) y gráficas planas ; sin embargo, una variación del problema en el que se requiere que el subgrafo esté conectado es NP-hard en gráficas planas. [7]
Más denso como máximo k subgrafo
El objetivo de lo más denso como máximo El problema es encontrar el subgrafo de densidad maxima en como mucho vértices. Anderson y Chellapilla demostraron que si existe un aproximación para este problema, entonces eso conducirá a una aproximación para los más densos problema de subgrafo.
Más denso al menos k subgrafo
El más denso al menos El problema se define de manera similar al más denso como máximo. problema de subgrafo. El problema es NP-completo, [8] pero admite aproximación 2 en tiempo polinomial. [9] Además, existe alguna evidencia de que este algoritmo de aproximación es esencialmente el mejor posible: asumiendo la Hipótesis de Expansión de Conjunto Pequeño (una suposición de complejidad computacional estrechamente relacionada con la Conjetura de Juegos Únicos ), entonces es NP-difícil aproximar el problema a dentro factor para cada constante . [10]
K -clique subgrafo más denso
Charalampos Tsourakakis presentó el-problema del subgrafo mas denso de la clica. Esta variación del problema del subgrafo más denso tiene como objetivo maximizar el número promedio de inducidos camarillas , dónde es el conjunto de -cliques inducidos por . Observe que el problema del subgrafo más denso se obtiene como un caso especial para. Esta generalización proporciona un enfoque politemporal empíricamente exitoso para extraer grandes casi camarillas de redes del mundo real a gran escala.
Localmente top- k subgrafo más denso
Qin y col. introdujo el problema del descubrimiento de subgráficos localmente más densos top-k en un gráfico, cada uno de los cuales alcanza la densidad más alta en su región local en el gráfico: no está contenido en ningún supergráfico con la misma o mayor densidad, ni contiene subgráficos con densidad estando vagamente conectado con el resto del subgrafo local más denso. Tenga en cuenta que el problema del subgrafo más denso se obtiene como un caso especial para. El conjunto de subgráficos localmente más densos en un gráfico se puede calcular en tiempo polinómico.
Referencias
- ^ Gallo, Giorgio; Grigoriadis, Michael D .; Tarjan, Robert E. (1989). "Un algoritmo y aplicaciones de flujo máximo paramétrico rápido". Revista SIAM de Computación . 18 (1): 30–55. doi : 10.1137 / 0218003 .
- ^ Charikar (2000). "Algoritmos de aproximación codiciosos para encontrar componentes densos en un gráfico". En Klaus Jansen; Samir Khuller (eds.). APROX '00: Actas del Tercer Taller Internacional sobre Algoritmos de Aproximación para la Optimización Combinatoria . Berlín, Heidelberg: Springer-Verlag. ISBN 978-3-540-67996-7.
- ^ Bhaskara, Aditya; Charikar, Moisés ; Chlamtáč, Edén; Feige, Uriel ; Vijayaraghavan, Aravindan (2010), "Detección de altas densidades logarítmicas: una aproximación de O ( n 1/4 ) para el subgrafo k más denso", STOC'10: Actas del Simposio Internacional ACM de 2010 sobre Teoría de la Computación , ACM, Nueva York , págs. 201–210, doi : 10.1145 / 1806689.1806719 , ISBN 9781450300506, MR 2743268.
- ^ Manurangsi, Pasin (2017), "Relación casi polinomial ETH-dureza del subgrafo k más denso aproximado", STOC'17 — Actas del 49º Simposio Anual ACM SIGACT sobre Teoría de la Computación , ACM, págs. 954–961, arXiv : 1611.05991 , doi : 10.1145 / 3055399.3055412 , ISBN 9781450345286.
- ^ Khot, Subhash (2006), "Descartando PTAS para gráficas de min-bisección, subgrafía k densa y camarilla bipartita", SIAM Journal on Computing , 36 (4): 1025–1071, CiteSeerX 10.1.1.114.3324 , doi : 10.1137 / S0097539705447037 , MR 2272270.
- ^ Corneil, DG ; Perl, Y. (1984), "Clustering and domination in perfect graphs", Discrete Applied Mathematics , 9 (1): 27–39, doi : 10.1016 / 0166-218X (84) 90088-X , MR 0754426.
- ^ Keil, J. Mark; Brecht, Timothy B. (1991), "La complejidad de la agrupación en gráficas planas" (PDF) , Journal of Combinatorial Mathematics and Combinatorial Computing , 9 : 155-159, MR 1111849.
- ^ Khuller, Samir ; Saha, Barna (2009), "Sobre la búsqueda de subgrafos densos" (PDF) , Autómatas, lenguajes y programación: 36 ° Coloquio Internacional, ICALP 2009, Rodas, Grecia, 5 al 12 de julio de 2009, Actas, Parte I , Notas de la conferencia en computadora Science, 5555 , Berlín: Springer-Verlag, págs. 597–608, CiteSeerX 10.1.1.722.843 , doi : 10.1007 / 978-3-642-02927-1_50 , ISBN 978-3-642-02926-4, MR 2544878
- ^ Anderson, Reid (2007), Encontrar subgrafos densos grandes y pequeños , arXiv : cs / 0702032 , Bibcode : 2007cs ........ 2032A
- ^ Manurangsi, Pasin (2017), Inapproximability of Maximum Biclique Problems, Mínimo k-Cut y Más denso al menos k-Subgraph de la hipótesis de expansión del conjunto pequeño , arXiv : 1705.03581 , Bibcode : 2017arXiv170503581M
Otras lecturas
- Anderson, R .; Chellapilla, K. (2009), "Encontrar subgráficos densos con límites de tamaño", WAW : 25–36.
- Feige, U .; Kortsarz, G .; Peleg, D. (1997), "The dense k -subgraph problem", Algorithmica , 29 (3): 410–421, CiteSeerX 10.1.1.25.9443 , doi : 10.1007 / s004530010050.
- Goldberg, AV (1984), "Encontrar un subgrafo de densidad máxima", Informe técnico.
- Tsourakakis, C. (2015), "The k -clique densest subgraph problem", The International World Wide Web Conference : 1122-1132, CiteSeerX 10.1.1.695.7667 , doi : 10.1145 / 2736277.2741098 , ISBN 9781450334693.
- Qin, Lu; Li, Rong-Hua; Chang, Lijun; Zhang, Chengqi (2015), "Locally Densest Subgraph Discovery", KDD , ACM, Nueva York: 965–974, doi : 10.1145 / 2783258.2783299 , ISBN 9781450336642.