En la informática teórica , el subgrafo isomorfismo problema es una tarea computacional en el que dos gráficos G y H se dan como entrada, y uno debe determinar si G contiene un subgrafo que es isomorfo a H . El isomorfismo de subgrafo es una generalización tanto del problema de la camarilla máxima como del problema de probar si un gráfico contiene un ciclo hamiltoniano y, por lo tanto, es NP-completo . [1] Sin embargo, algunos otros casos de isomorfismo de subgrafo pueden resolverse en tiempo polinomial. [2]
A veces, la coincidencia de subgrafos de nombre también se utiliza para el mismo problema. Este nombre pone énfasis en encontrar tal subgrafo en oposición al problema de decisión simple.
Problema de decisión y complejidad computacional
Para probar que el isomorfismo del subgrafo es NP-completo, debe formularse como un problema de decisión . La entrada para el problema de decisión es un par de gráficos G y H . La respuesta al problema es positiva si H es isomorfo a un subgrafo de G y negativa en caso contrario.
Pregunta formal:
Dejar , ser gráficos. Hay un subgrafo tal que ? Es decir, ¿existe una biyección? tal que ?
La prueba de que el isomorfismo del subgrafo es NP-completo es simple y se basa en la reducción del problema de la camarilla , un problema de decisión NP-completo en el que la entrada es un solo gráfico G y un número k , y la pregunta es si G contiene un subgrafo completo con k vértices. Para traducir esto a un problema de isomorfismo de subgrafo, simplemente sea H el grafo completo K k ; entonces la respuesta al problema de isomorfismo del subgrafo para G y H es igual a la respuesta al problema de clique para G y k . Dado que el problema de la camarilla es NP-completo, esta reducción del polinomio-tiempo muchos-uno muestra que el isomorfismo del subgrafo también es NP-completo. [3]
Una reducción alternativa de la ciclo hamiltoniano problema se traduce en una gráfica G que va a ser probado para Hamiltonicity en el par de gráficos G y H , donde H es un ciclo que tienen el mismo número de vértices como G . Debido a que el problema del ciclo hamiltoniano es NP-completo incluso para gráficas planas , esto muestra que el isomorfismo del subgrafo permanece NP-completo incluso en el caso planar. [4]
El isomorfismo del grafo es una generalización del problema del isomorfismo del grafo , que pregunta si G es isomorfo a H : la respuesta al problema del isomorfismo del grafo es verdadera si y solo si G y H tienen el mismo número de vértices y aristas y el problema del isomorfismo del subgrafo para G y H es cierto. Sin embargo, el estado de la teoría de la complejidad del isomorfismo de grafos sigue siendo una cuestión abierta.
En el contexto de la conjetura de Aanderaa-Karp-Rosenberg sobre la complejidad de la consulta de las propiedades de los grafos monótonos, Gröger (1992) mostró que cualquier problema de isomorfismo de subgrafo tiene una complejidad de consulta Ω ( n 3/2 ); es decir, resolver el isomorfismo del subgrafo requiere un algoritmo para verificar la presencia o ausencia en la entrada de Ω ( n 3/2 ) aristas diferentes en el gráfico. [5]
Algoritmos
Ullmann (1976) describe un procedimiento de retroceso recursivo para resolver el problema de isomorfismo del subgrafo. Aunque su tiempo de ejecución es, en general, exponencial, se necesita un tiempo polinomial para cualquier elección fija de H (con un polinomio que depende de la elección de H ). Cuando G es un gráfico plano (o más generalmente un gráfico de expansión acotada ) y H es fijo, el tiempo de ejecución del isomorfismo del subgráfico se puede reducir a tiempo lineal . [2]
Ullmann (2010) es una actualización sustancial del artículo sobre el algoritmo de isomorfismo de subgrafo de 1976.
Cordella (2004) propuso en 2004 otro algoritmo basado en el de Ullmann, VF2, que mejora el proceso de refinamiento utilizando diferentes heurísticas y utiliza significativamente menos memoria.
Bonnici (2013) propuso un algoritmo mejor, que mejora el orden inicial de los vértices utilizando algunas heurísticas.
Para gráficos grandes, los algoritmos de vanguardia incluyen CFL-Match y Turboiso, y extensiones como DAF de Han (2019). .
Aplicaciones
Como subgrafo se ha aplicado isomorfismo en el área de la quiminformática para encontrar similitudes entre compuestos químicos a partir de su fórmula estructural; a menudo en esta área se utiliza el término búsqueda de subestructura . [6] Una estructura de consulta a menudo se define gráficamente usando un programa editor de estructura ; Los sistemas de bases de datos basados en SMILES suelen definir consultas utilizando SMARTS , una extensión de SMILES .
El problema estrechamente relacionado de contar el número de copias isomórficas de un gráfico H en un gráfico G más grande se ha aplicado al descubrimiento de patrones en bases de datos, [7] la bioinformática de redes de interacción proteína-proteína, [8] y en métodos de gráficos aleatorios exponenciales. para modelar matemáticamente redes sociales . [9]
Ohlrich y col. (1993) describen una aplicación del isomorfismo de subgrafo en el diseño asistido por computadora de circuitos electrónicos . La coincidencia de subgrafos es también un subpaso en la reescritura de gráficos (el más intensivo en tiempo de ejecución) y, por lo tanto, lo ofrecen las herramientas de reescritura de gráficos .
El problema también es de interés en la inteligencia artificial , donde se considera parte de una serie de problemas de coincidencia de patrones en gráficos; una extensión del isomorfismo de subgrafo conocida como minería de grafos también es de interés en esa área. [10]
Ver también
- Minería frecuente de subárboles
- Problema de isomorfismo de subgrafo inducido
- Problema de subgrafo de borde común máximo
- Problema de isomorfismo de subgrafo común máximo
Notas
- ↑ El artículo original de Cook (1971) que prueba el teorema de Cook-Levin ya mostraba que el isomorfismo del subgrafo era NP-completo, usando una reducción de 3-SAT que involucra camarillas.
- ↑ a b Eppstein (1999) ; Nešetřil y Ossona de Mendez (2012)
- ^ Wegener, Ingo (2005), Teoría de la complejidad: exploración de los límites de los algoritmos eficientes , Springer, p. 81, ISBN 9783540210450.
- ^ de la Higuera, Colin; Janodet, Jean-Christophe; Samuel, Émilie; Damiand, Guillaume; Solnon, Christine (2013), "Algoritmos polinomiales para isomorfismos de grafos y subgrafos de plano abierto" (PDF) , Informática teórica , 498 : 76–99, doi : 10.1016 / j.tcs.2013.05.026 , MR 3083515 ,
Se conoce desde mediados de los años 70 que el problema de isomorfismo se puede resolver en tiempo polinomial para gráficas planas. Sin embargo, también se ha observado que el problema del subisomorfismo sigue siendo N P-completo, en particular porque el problema del ciclo hamiltoniano es NP-completo para gráficas planas.
- ^ Aquí Ω invoca la notación Big Omega .
- ↑ Ullmann (1976)
- ^ Kuramochi y Karypis (2001) .
- ^ Pržulj, Corneil y Jurisica (2006) .
- ^ Snijders y col. (2006) .
- ^ http://www.aaai.org/Papers/Symposia/Fall/2006/FS-06-02/FS06-02-007.pdf ; versión ampliada en https://e-reports-ext.llnl.gov/pdf/332302.pdf
Referencias
- Cook, SA (1971), "La complejidad de los procedimientos de demostración de teoremas" , Proc. 3er Simposio ACM sobre Teoría de la Computación , págs. 151-158, doi : 10.1145 / 800157.805047.
- Eppstein, David (1999), "Isomorfismo de subgrafo en gráficas planas y problemas relacionados" (PDF) , Journal of Graph Algorithms and Applications , 3 (3): 1–27, arXiv : cs.DS / 9911003 , doi : 10.7155 / jgaa .00014.
- Garey, Michael R .; Johnson, David S. (1979), Computadoras e intratabilidad: una guía para la teoría de NP-Completeness , WH Freeman, ISBN 978-0-7167-1045-5. A1.4: GT48, pág.202.
- Gröger, Hans Dietmar (1992), "Sobre la complejidad aleatoria de las propiedades de los gráficos monótonos" (PDF) , Acta Cybernetica , 10 (3): 119-127.
- Han, Myoungji; Kim, Hyunjoon; Gu, Geonmo; Park, Kunsoo; Han, Wookshin (2019), "Emparejamiento eficiente de subgrafos: armonización de la programación dinámica, orden de emparejamiento adaptativo y conjunto de fallas", SIGMOD , doi : 10.1145 / 3299869.3319880
- Kuramochi, Michihiro; Karypis, George (2001), "Descubrimiento frecuente de subgrafos", 1ª Conferencia Internacional IEEE sobre Minería de Datos , p. 313, CiteSeerX 10.1.1.22.4992 , doi : 10.1109 / ICDM.2001.989534 , ISBN 978-0-7695-1119-1.
- Ohlrich, Miles; Ebeling, Carl; Ginting, Eka; Sather, Lisa (1993), "SubGemini: identificación de subcircuitos mediante un algoritmo de isomorfismo de subgraph rápido", Actas de la 30ª Conferencia internacional de automatización del diseño , págs. 31-37, doi : 10.1145 / 157485.164556 , ISBN 978-0-89791-577-9.
- Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), "18.3 El problema del isomorfismo del subgrafo y las consultas booleanas", Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, 28 , Springer, págs. 400–401, doi : 10.1007 / 978-3 -642-27875-4 , ISBN 978-3-642-27874-7, MR 2920058.
- Pržulj, N .; Corneil, DG ; Jurisica, I. (2006), "Estimación eficiente de las distribuciones de frecuencia de graphlet en redes de interacción proteína-proteína", Bioinformatics , 22 (8): 974–980, doi : 10.1093 / bioinformatics / btl030 , PMID 16452112.
- Snijders, TAB; Pattison, PE; Robins, G .; Handcock, MS (2006), "Nuevas especificaciones para modelos de gráficos aleatorios exponenciales", Metodología sociológica , 36 (1): 99–153, CiteSeerX 10.1.1.62.7975 , doi : 10.1111 / j.1467-9531.2006.00176.x.
- Ullmann, Julian R. (1976), "Un algoritmo para el isomorfismo de subgrafo", Journal of the ACM , 23 (1): 31–42, doi : 10.1145 / 321921.321925.
- Jamil, Hasan (2011), "Cálculo de consultas isomórficas de subgrafo utilizando unificación estructural y estructuras gráficas mínimas", 26º Simposio ACM sobre Computación Aplicada , págs. 1058–1063.
- Ullmann, Julian R. (2010), "Algoritmos de vector de bits para satisfacción de restricciones binarias e isomorfismo de subgrafo", Journal of Experimental Algorithmics , 15 : 1.1, CiteSeerX 10.1.1.681.8766 , doi : 10.1145 / 1671970.1921702.
- Cordella, Luigi P. (2004), "Un algoritmo de isomorfismo (sub) gráfico para hacer coincidir gráficos grandes", IEEE Transactions on Pattern Analysis and Machine Intelligence , 26 (10): 1367-1372, CiteSeerX 10.1.1.101.5342 , doi : 10.1109 / tpami.2004.75 , PMID 15641723
- Bonnici, V .; Giugno, R. (2013), "Un algoritmo de isomorfismo de subgrafo y su aplicación a datos bioquímicos", BMC Bioinformatics , 14 (Suppl7) (13): S13, doi : 10.1186 / 1471-2105-14-s7-s13 , PMC 3633016 , PMID 23815292
- Carletti, V .; Foggia, P .; Saggese, A .; Vento, M. (2018), "Desafiando la complejidad temporal del isomorfismo de subgrafo exacto para gráficos enormes y densos con VF3", IEEE Transactions on Pattern Analysis and Machine Intelligence , 40 (4): 804–818, doi : 10.1109 / TPAMI. 2017.2696940 , PMID 28436848