Problema de isomorfismo de subgrafos

Problema en informática teórica

En informática teórica , el problema del isomorfismo de subgrafos es una tarea computacional en la que se dan como entrada dos grafos G y H , y se debe determinar si G contiene un subgrafo que es isomorfo a H. El isomorfismo de subgrafos es una generalización tanto del problema de la camarilla máxima como del problema de comprobar si un grafo contiene un ciclo hamiltoniano y, por tanto, es NP-completo . ^[1] Sin embargo, ciertos otros casos de isomorfismo de subgrafos pueden resolverse en tiempo polinomial. ^[2]

A veces, también se utiliza el nombre de coincidencia de subgrafos para el mismo problema. Este nombre pone énfasis en la búsqueda de dicho subgrafo en lugar de en el problema de decisión simple.

Problema de decisión y complejidad computacional

Para demostrar que el isomorfismo de subgrafos es NP-completo, debe formularse como un problema de decisión . La entrada al problema de decisión es un par de grafos 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:

Sean grafos . ¿Existe un subgrafo tal que ? Es decir, ¿existe una biyección tal que ? ${\displaystyle G=(V,E)}$ ${\displaystyle H=(V^{\prime },E^{\prime })}$ ${\displaystyle G_{0}=(V_{0},E_{0})\mid V_{0}\subseteq V,E_{0}\subseteq E\cap (V_{0}\times V_{0})}$ ${\displaystyle G_{0}\cong H}$ ${\displaystyle f\colon V_{0}\rightarrow V^{\prime }}$ ${\displaystyle \{\,v_{1},v_{2}\,\}\in E_{0}\iff \{\,f(v_{1}),f(v_{2})\,\}\in E^{\prime }}$

La prueba de que el isomorfismo de subgrafos 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 grafo 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 subgrafos, simplemente sea H el grafo completo K _k ; entonces la respuesta al problema de isomorfismo de subgrafos para G y H es igual a la respuesta al problema de la camarilla para G y k . Dado que el problema de la camarilla es NP-completo, esta reducción de muchos-uno en tiempo polinomial muestra que el isomorfismo de subgrafos también es NP-completo. ^[3]

Una reducción alternativa del problema del ciclo hamiltoniano traduce un grafo G cuya hamiltonicidad se va a probar en el par de grafos G y H , donde H es un ciclo que tiene el mismo número de vértices que G . Debido a que el problema del ciclo hamiltoniano es NP-completo incluso para grafos planares , esto demuestra que el isomorfismo de subgrafos sigue siendo NP-completo incluso en el caso planar. ^[4]

El isomorfismo de subgrafos es una generalización del problema de isomorfismo de grafos , que pregunta si G es isomorfo a H : la respuesta al problema de isomorfismo de grafos es verdadera si y solo si G y H tienen ambos el mismo número de vértices y aristas y el problema de isomorfismo de subgrafos para G y H es verdadero. Sin embargo, el estado de 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 consulta de las propiedades de grafos monótonos, Gröger (1992) mostró que cualquier problema de isomorfismo de subgrafos tiene una complejidad de consulta Ω( n ^3/2 ); es decir, resolver el isomorfismo de subgrafos requiere un algoritmo para verificar la presencia o ausencia en la entrada de Ω( n ^3/2 ) aristas diferentes en el grafo. ^[5]

Algoritmos

Ullmann (1976) describe un procedimiento de retroceso recursivo para resolver el problema del isomorfismo de subgrafos. Aunque su tiempo de ejecución es, en general, exponencial, requiere 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 grafo plano (o más generalmente un grafo de expansión acotada ) y H es fijo, el tiempo de ejecución del isomorfismo de subgrafos se puede reducir a un tiempo lineal . ^[2]

Ullmann (2010) es una actualización sustancial del artículo de 1976 sobre el algoritmo de isomorfismo de subgrafos.

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 y Giugno (2013) propusieron un mejor algoritmo, que mejora el orden inicial de los vértices utilizando algunas heurísticas.

El solucionador de última generación para instancias difíciles de tamaño moderado es el Glasgow Subgraph Solver (McCreesh, Prosser y Trimble (2020)). ^[6] Este solucionador adopta un enfoque de programación de restricciones, utilizando estructuras de datos de bits paralelos y algoritmos de propagación especializados para el rendimiento. Admite las variaciones más comunes del problema y es capaz de contar o enumerar soluciones, así como de decidir si existe alguna.

Para gráficos grandes, los algoritmos de última generación incluyen CFL-Match y Turboiso, y extensiones de estos como DAF de Han et al. (2019).

Aplicaciones

Como el isomorfismo de subgrafos se ha aplicado en el área de la quimioinformá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 . ^[7] Una estructura de consulta a menudo se define gráficamente utilizando un programa editor de estructuras ; los sistemas de bases de datos basados ​​en SMILES generalmente definen 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 más grande G se ha aplicado al descubrimiento de patrones en bases de datos, ^[8] la bioinformática de redes de interacción proteína-proteína, ^[9] y en métodos de gráficos aleatorios exponenciales para modelar matemáticamente redes sociales . ^[10]

Ohlrich et al. (1993) describen una aplicación del isomorfismo de subgrafos en el diseño asistido por computadora de circuitos electrónicos . La correspondencia de subgrafos también es un subpaso en la reescritura de grafos (el que requiere más tiempo de ejecución) y, por lo tanto, lo ofrecen las herramientas de reescritura de grafos .

El problema también es de interés en la inteligencia artificial , donde se lo considera parte de una serie de problemas de coincidencia de patrones en gráficos; una extensión del isomorfismo de subgrafos conocida como minería de gráficos también es de interés en esa área. ^[11]

Véase también

• Minería frecuente de subárboles
• Problema de isomorfismo de subgrafos inducidos
• Problema de subgrafo de arista común máxima
• Problema de isomorfismo del subgrafo común máximo

Notas

1. El artículo original de Cook (1971) que prueba el teorema de Cook-Levin ya mostraba que el isomorfismo de subgrafos era NP-completo, utilizando una reducción de 3-SAT que involucraba camarillas.
2. Eppstein (1999); Nešetřil & Ossona de Méndez (2012)
3. Wegener, Ingo (2005), Teoría de la complejidad: exploración de los límites de los algoritmos eficientes, Springer, pág. 81, ISBN 9783540210450.
4. de la Higuera, Colin; Janodet, Jean-Christophe; Samuel, Émilie; Damiand, Guillaume; Solnon, Christine (2013), "Polynomial algorithms for open plane graph and subgraph isomorphisms" (PDF) , Theoretical Computer Science , 498 : 76–99, doi : 10.1016/j.tcs.2013.05.026 , MR  3083515, Se sabe desde mediados de los años 70 que el problema del isomorfismo es solucionable en tiempo polinomial para grafos planos. 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 grafos planares.
5. Aquí Ω invoca la notación Big Omega .
6. Para una evaluación experimental, véase Solnon (2019).
7. Ullmann (1976)
8. Kuramochi y Karypis (2001).
9. Pržulj, Corneil y Jurisica (2006).
10. Snijders y otros (2006).
11. 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. 3rd ACM Symposium on Theory of Computing , págs. 151–158, doi : 10.1145/800157.805047 , S2CID  7573663.
• Eppstein, David (1999), "Isomorfismo de subgrafos en grafos planares y problemas relacionados" (PDF) , Journal of Graph Algorithms and Applications , 3 (3): 1–27, arXiv : cs.DS/9911003 , doi :10.7155/jgaa.00014, S2CID  2303110.
• Garey, Michael R.; Johnson , David S. (1979), Computadoras e intratabilidad: una guía para la teoría de la NP-completitud , 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), "Coincidencia eficiente de subgrafos: armonización de la programación dinámica, el orden de coincidencia adaptativo y la unión de conjuntos fallidos", SIGMOD , doi : 10.1145/3299869.3319880, S2CID  195259296
• Kuramochi, Michihiro; Karypis, George (2001), "Descubrimiento frecuente de subgrafos", 1.ª Conferencia internacional IEEE sobre minería de datos , pág. 313, CiteSeerX  10.1.1.22.4992 , doi :10.1109/ICDM.2001.989534, ISBN 978-0-7695-1119-1, Número de identificación del sujeto  8684662.
• Ohlrich, Miles; Ebeling, Carl; Ginting, Eka; Sather, Lisa (1993), "SubGemini: identificación de subcircuitos utilizando un algoritmo rápido de isomorfismo de subgrafos", 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, Número de identificación del sujeto  5889119.
• Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), "18.3 El problema del isomorfismo de subgrafos y las consultas booleanas", Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, vol. 28, Springer, págs. 400–401, doi :10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, Sr.  2920058.
• Pržulj, N.; Corneil, DG ; Jurisica, I. (2006), "Estimación eficiente de distribuciones de frecuencias de grafitos 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, S2CID  10800726.
• Ullmann, Julian R. (1976), "Un algoritmo para el isomorfismo de subgrafos", Journal of the ACM , 23 (1): 31–42, doi : 10.1145/321921.321925 , S2CID  17268751.
• Jamil, Hasan (2011), "Cálculo de consultas isomórficas de subgrafos mediante unificación estructural y estructuras de grafos mínimas", 26.º Simposio ACM sobre informática aplicada , págs. 1058-1063.
• Ullmann, Julian R. (2010), "Algoritmos de vectores de bits para la satisfacción de restricciones binarias y el isomorfismo de subgrafos", Journal of Experimental Algorithmics , 15 : 1.1, CiteSeerX  10.1.1.681.8766 , doi : 10.1145/1671970.1921702, S2CID  15021184.
• Cordella, Luigi P. (2004), "Un algoritmo de isomorfismo de (sub)grafos para la correspondencia de grafos 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, S2CID  833657
• Bonnici, V.; Giugno, R. (2013), "Un algoritmo de isomorfismo de subgrafos 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 subgrafos exactos para grafos grandes y densos con VF3", IEEE Transactions on Pattern Analysis and Machine Intelligence , 40 (4): 804–818, doi :10.1109/TPAMI.2017.2696940, PMID  28436848, S2CID  3709576
• Solnon, Christine (2019), "Experimental Evaluation of Subgraph Isomorphism Solvers" (PDF) , Graph-Based Representations in Pattern Recognition - 12th IAPR-TC-15 International Workshop, GbRPR 2019, Tours, Francia, 19-21 de junio de 2019, Actas , Lecture Notes in Computer Science, vol. 11510, Springer, págs. 1–13, doi :10.1007/978-3-030-20081-7_1, ISBN 978-3-030-20080-0, Número de identificación del sujeto  128270779
• McCreesh, Ciaran; Prosser, Patrick; Trimble, James (2020), "El solucionador de subgrafos de Glasgow: uso de programación con restricciones para abordar variantes de problemas de isomorfismo de subgrafos difíciles", Graph Transformation - 13th International Conference, ICGT 2020, celebrada como parte de STAF 2020, Bergen, Noruega, 25 y 26 de junio de 2020, Actas , Lecture Notes in Computer Science, vol. 12150, Springer, págs. 316–324, doi : 10.1007/978-3-030-51372-6_19 , ISBN 978-3-030-51371-9