problema de isomorfismo de subgrafos

En la ciencia de la computación teórica , el problema del isomorfismo de subgrafos es una tarea computacional en la que dos grafos${\displaystyle G}$y${\displaystyle H}$se proporcionan como entrada, y uno debe determinar si${\displaystyle G}$contiene un subgrafo que es isomorfo a${\displaystyle 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 lo tanto es NP-completo . ^{[ 1 ]} Sin embargo, otros casos de isomorfismo de subgrafos pueden resolverse en tiempo polinomial. ^{[ 2 ]}

En ocasiones, también se utiliza el término " coincidencia de subgrafos" para referirse al mismo problema. Este nombre pone énfasis en encontrar dicho subgrafo, en contraposición al problema de decisión simple.

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.${\displaystyle 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${\displaystyle G=(V,E)}$,${\displaystyle H=(V^{\prime },E^{\prime })}$ser gráficos. ¿Hay un subgrafo?${\displaystyle G_{0}=(V_{0},E_{0})\mid V_{0}\subseteq V,E_{0}\subseteq E\cap (V_{0}\times V_{0})}$de tal manera que${\displaystyle G_{0}\cong H}$¿Es decir, existe una biyección ?${\displaystyle f\colon V_{0}\rightarrow V^{\prime }}$de tal manera que${\displaystyle \{\,v_{1},v_{2}\,\}\in E_{0}\iff \{\,f(v_{1}),f(v_{2})\,\}\in E^{\prime }}$¿

La demostración de que el isomorfismo de subgrafos es NP-completo es sencilla 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 único 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 a 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 transforma un grafo G que se va a probar para determinar su hamiltonicidad en el par de grafos G y H , donde H es un ciclo con el mismo número de vértices que G. Dado 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 del isomorfismo de grafos , que plantea la cuestión de si G es isomorfo a H : la respuesta al problema del isomorfismo de grafos es verdadera si y solo si G y H tienen el mismo número de vértices y aristas, y el problema del isomorfismo de subgrafos para G y H es verdadero. Sin embargo, el estatus del isomorfismo de grafos desde el punto de vista de la teoría de la complejidad sigue siendo una cuestión abierta.

En el contexto de la conjetura de Aanderaa–Karp–Rosenberg sobre la complejidad de consulta de las propiedades monótonas de los grafos, Gröger (1992) demostró 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 comprobar la presencia o ausencia en la entrada de Ω( n ^3/2 ) aristas diferentes en el grafo. ^{[ 5 ]}

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 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 planar (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 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) ^{[ 6 ] [ 7 ]} propusieron un algoritmo mejor, que mejora el orden inicial de los vértices utilizando algunas heurísticas.

El solucionador más avanzado actualmente para instancias difíciles de tamaño moderado es el Glasgow Subgraph Solver ( McCreesh, Prosser y Trimble (2020) ). ^{[ 8 ]} Este solucionador adopta un enfoque de programación con restricciones , utilizando estructuras de datos paralelas a nivel de bits y algoritmos de propagación especializados para optimizar el rendimiento. Admite la mayoría de las variantes comunes del problema y es capaz de contar o enumerar soluciones, así como de determinar si existe alguna.

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

Inspirado en enfoques basados ​​en programación de restricciones y la metodología DAF, ArcMatch ^{[ 9 ]} introdujo una técnica de reducción que opera en caminos del llamado "grafo de dominio", una estructura de datos compuesta por dominios de vértices y aristas.

Dado que el isomorfismo de subgrafos se ha aplicado en el campo de la quimioinformática para encontrar similitudes entre compuestos químicos a partir de su fórmula estructural , en este ámbito se suele utilizar el término búsqueda de subestructuras . ^{[ 10 ]} La estructura de una consulta se define a menudo gráficamente mediante un programa editor de estructuras ; los sistemas de bases de datos basados ​​en SMILES suelen definir las consultas utilizando SMARTS , una extensión de SMILES .

El problema estrechamente relacionado de contar el número de copias isomorfas de un grafo H en un grafo más grande G se ha aplicado al descubrimiento de patrones en bases de datos, ^{[ 11 ]} la bioinformática de redes de interacción proteína-proteína, ^{[ 12 ]} y en métodos de grafos aleatorios exponenciales para modelar matemáticamente redes sociales . ^{[ 13 ]}

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 consume 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 inteligencia artificial , donde se considera parte de un conjunto de problemas de coincidencia de patrones en grafos; una extensión del isomorfismo de subgrafos conocida como minería de grafos también es de interés en esa área. ^{[ 14 ]}

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

• Cook, SA (1971), "La complejidad de los procedimientos de demostración de teoremas" , Actas del 3er Simposio ACM sobre Teoría de la Computación , 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), Computers and Intractability: A Guide to the Theory of 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 grafos monótonos" ( PDF) , Acta Cybernetica , 10 (3): 119–127.
• Han, Myoungji; Kim, Hyunjoon; Gu, Geonmo; Park, Kunsoo; Han, Wookshin (2019), Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together , doi : 10.1145/3299869.3319880 , S2CID 195259296 
• Kuramochi, Michihiro; Karypis, George (2001), "Frequent subgraph discovery", 1st IEEE International Conference on Data Mining , p.  313, CiteSeerX 10.1.1.22.4992 , doi : 10.1109/ICDM.2001.989534 , ISBN  978-0-7695-1119-1, S2CID 8684662 .
• Ohlrich, Miles; Ebeling, Carl; Ginting, Eka; Sather, Lisa (1993), "SubGemini: identificación de subcircuitos mediante 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, S2CID 5889119 .
• Nešetřil, Jaroslav ; Ossona de Méndez, 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, pp. 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 distribuciones de frecuencia de grafos 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 grafos aleatorios exponenciales", Sociological Methodology , 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ínimos", 26.º Simposio ACM sobre Computación Aplicada , págs. 1058–1063 .
• Ullmann, Julian R. (2010), "Algoritmos de vector de bits para la satisfacción de restricciones binarias e 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, Bibcode : 2004ITPAM..26.1367C , 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 (Supl. 7): 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 exacto de subgrafos para grafos enormes y densos con VF3", IEEE Transactions on Pattern Analysis and Machine Intelligence , 40 (4): 804– 818, Bibcode : 2018ITPAM..40..804C , doi : 10.1109/TPAMI.2017.2696940 , PMID 28436848 , S2CID 3709576  
• Solnon, Christine (2019), "Evaluación experimental de solucionadores de isomorfismo de subgrafos" , Representaciones basadas en grafos en el reconocimiento de patrones - 12.º Taller Internacional IAPR-TC-15, GbRPR 2019, Tours, Francia, 19-21 de junio de 2019, Actas , Lecture Notes in Computer Science, vol.  11510, Springer, pp. 1–13 , doi : 10.1007/978-3-030-20081-7_1 , ISBN  978-3-030-20080-0, S2CID 128270779 
• McCreesh, Ciaran; Prosser, Patrick; Trimble, James (2020), "The Glasgow Subgraph Solver: Using Constraint Programming to Tackle Hard Subgraph Isomorphism Problem Variants", Graph Transformation - 13th International Conference, ICGT 2020, Held as Part of STAF 2020, Bergen, Norway, June 25-26, 2020, Proceedings , Lecture Notes in Computer Science, vol.  12150, Springer, pp. 316–324 , doi : 10.1007/978-3-030-51372-6_19 , ISBN  978-3-030-51371-9, PMC 7314700 
• Bonnici, V., Grasso, R., Micale, G. et al. ArcMatch : emparejamiento de subgrafos de alto rendimiento para grafos etiquetados mediante la explotación de dominios de aristas. Data Min Knowl Disc 38 , 3868–3921 (2024). https://doi.org/10.1007/s10618-024-01061-8