Problema de isomorfismo de subgrafos

Problema en informática teórica.

En informática teórica , el problema de isomorfismo de subgrafos es una tarea computacional en la que se dan como entrada dos gráficos G y H , y se debe determinar si G contiene un subgrafo que sea isomorfo a H. El isomorfismo de subgrafos 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 subgrafos pueden resolverse en tiempo polinomial. ^[2]

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

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 gráficos G y H. La respuesta al problema es positiva si H es isomorfa a un subgrafo de G y negativa en caso contrario.

Pregunta formal:

Sean , gráficas. ¿Existe un subgrafo tal ? 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 del subgrafo es NP-completo es simple y se basa en la reducción del problema de camarilla , un problema de decisión NP-completo en el que la entrada es un gráfico único 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 gráfico completo K _k ; entonces la respuesta al problema de isomorfismo de subgrafos para G y H es igual a la respuesta al problema de camarilla para G y k . Dado que el problema de camarilla es NP-completo, esta reducción de muchos en tiempo polinómico muestra que el isomorfismo de subgrafos también es NP-completo. ^[3]

Una reducción alternativa del problema del ciclo hamiltoniano traduce un gráfico G cuya hamiltonicidad se va a probar en el par de gráficos 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 gráficos planos , esto muestra que el isomorfismo de subgrafos sigue siendo NP completo incluso en el caso plano. ^[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 sólo si G y H tienen el mismo número de vértices y aristas y el problema de isomorfismo de subgrafos para G y H es cierto. Sin embargo, el estatus teórico 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 gráficos monótonos, Gröger (1992) demostró que cualquier problema de isomorfismo de subgrafos tiene una complejidad de la 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 ) diferentes aristas en el gráfico. ^[5]

Algoritmos

Ullmann (1976) describe un procedimiento de retroceso recursivo para resolver el problema de isomorfismo de subgrafos. Aunque su tiempo de ejecución es, en general, exponencial, se necesita tiempo polinómico 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 subgrafo se puede reducir a tiempo lineal . ^[2]

Ullmann (2010) es una actualización sustancial del artículo sobre algoritmo de isomorfismo de subgrafos 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 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 actual para instancias difíciles de tamaño moderado es el Glasgow Subgraph Solver (McCreesh, Prosser & 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 decidir si existe alguna.

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

Aplicaciones

Como subgrafo, el isomorfismo se ha aplicado en el área de la quimioinformática para encontrar similitudes entre compuestos químicos a partir de su fórmula estructural; En este ámbito se utiliza a menudo el término búsqueda de subestructuras . ^[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 normalmente 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 de circuitos electrónicos asistido por computadora . La coincidencia de subgrafos también es un subpaso en la reescritura de gráficos (el que requiere más 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 subgrafos conocida como minería de grafos también es de interés en esa área. ^[11]

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

1. El artículo original de Cook (1971) que prueba el teorema de Cook-Levin ya mostró que el isomorfismo de subgrafos es NP-completo, utilizando una reducción de 3-SAT que involucra 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. 81, ISBN 9783540210450.
4. de la Higuera, Colin; Janodet, Jean-Christophe; Samuel, Emilia; Damiand, Guillaume; Solnon, Christine (2013), "Algoritmos polinomiales para isomorfismos de subgrafos y gráficos de plano abierto" (PDF) , Ciencias de la Computación Teórica , 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 se puede resolver en tiempo polinómico para gráficas planas. Sin embargo, también se ha observado que el problema del subisomorfismo sigue siendo NP-completo, en particular porque el problema del ciclo hamiltoniano es NP-completo para gráficos planos.
5. Aquí Ω invoca la notación Big Omega .
6. Para una evaluación experimental, consulte Solnon (2019).
7. Ullmann (1976)
8. Kuramochi y Karypis (2001).
9. Pržulj, Corneil y Jurisica (2006).
10. Snijders y col. (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. 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 gráficos planos 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 integridad NP , 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; Parque, Kunsoo; Han, Wookshin (2019), "Coincidencia eficiente de subgrafos: armonización de la programación dinámica, orden de coincidencia adaptativo y conjunto fallido", SIGMOD , doi :10.1145/3299869.3319880, S2CID  195259296
• Kuramochi, Michihiro; Karypis, George (2001), "Descubrimiento frecuente de subgrafos", Primera 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, S2CID  8684662.
• Ohlrich, millas; Ebeling, Carl; Ginting, Eka; Sather, Lisa (1993), "SubGemini: identificación de subcircuitos utilizando un algoritmo de isomorfismo de subgrafo 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, S2CID  5889119.
• Nešetřil, Jaroslav ; Ossona de Méndez, Patrice (2012), "18.3 El problema del isomorfismo de subgrafos y 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, señor  2920058.
• Pržulj, N.; Corneil, DG ; Jurisica, I. (2006), "Estimación eficiente de distribuciones de frecuencia 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), "Computación de consultas isomórficas de subgrafos utilizando unificación estructural y estructuras de gráficos mínimas", 26º Simposio ACM sobre informática aplicada , págs..
• Ullmann, Julian R. (2010), "Algoritmos de vector de bits para 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) 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, 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 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, S2CID  3709576
• Solnon, Christine (2019), "Evaluación experimental de solucionadores de isomorfismo de subgrafos" (PDF) , Representaciones basadas en gráficos en el reconocimiento de patrones - 12.º taller internacional IAPR-TC-15, GbRPR 2019, Tours, Francia, 19 al 21 de junio de 2019, Actas , Apuntes de conferencias sobre informática, vol. 11510, Springer, págs. 1 a 13, doi :10.1007/978-3-030-20081-7_1, ISBN 978-3-030-20080-0, S2CID  128270779
• McCreesh, Ciaran; Prosser, Patricio; Trimble, James (2020), "The Glasgow Subgraph Solver: Uso de la programación de restricciones para abordar variantes de problemas de isomorfismo de subgrafos difíciles", Graph Transformation - 13.ª Conferencia Internacional, ICGT 2020, celebrada como parte de STAF 2020, Bergen, Noruega, 25 y 26 de junio , 2020, Actas , Apuntes de conferencias sobre informática, vol. 12150, Springer, págs. 316–324, doi : 10.1007/978-3-030-51372-6_19 , ISBN 978-3-030-51371-9