subgrafo inducido común máximo

En teoría de grafos y ciencias de la computación teórica , un subgrafo inducido común máximo de dos grafos G y H es un grafo que es un subgrafo inducido tanto de G como de H , y que tiene tantos vértices como sea posible.

Encontrar este grafo es NP-difícil . En el problema de decisión asociado , la entrada son dos grafos G y H y un número k . El problema es decidir si G y H tienen un subgrafo inducido común con al menos k vértices. Este problema es NP-completo . ^{[ 1 ]} Es una generalización del problema de isomorfismo de subgrafos inducidos , que surge cuando k es igual al número de vértices en el menor de G y H , de modo que todo este grafo debe aparecer como un subgrafo inducido del otro grafo.

Basándonos en los resultados de dificultad de aproximación para el problema del conjunto independiente máximo , el problema del subgrafo inducido común máximo también es difícil de aproximar. ^{[ 2 ]} Esto implica que, a menos que P = NP , no existe ningún algoritmo de aproximación que, en tiempo polinomial ,${\displaystyle n}$-grafos de vértices, siempre encuentra una solución dentro de un factor de${\displaystyle n^{1-\epsilon }}$de óptimo, para cualquier${\displaystyle \epsilon >0}$. ^{[ 3 ]}

Una posible solución para este problema es construir un grafo de producto modular de G y H. En este grafo, la camarilla más grande corresponde a un subgrafo inducido común máximo de G y H. Por lo tanto, se pueden usar algoritmos para encontrar camarillas máximas para encontrar el subgrafo inducido común máximo. ^{[ 4 ]} Además, se puede usar un algoritmo de camarilla máxima modificado para encontrar un subgrafo conexo común máximo . ^{[ 5 ]}

El algoritmo McSplit (junto con su variante McSplit↓) es un algoritmo de verificación hacia adelante que no utiliza la codificación de clique, sino una estructura de datos compacta para realizar un seguimiento de los vértices del grafo H a los que se puede asignar cada vértice del grafo G. Ambas versiones del algoritmo McSplit superan a la codificación de clique para muchas clases de grafos. ^{[ 6 ]} Una implementación más eficiente de McSplit es McSplitDAL+PR, que combina un agente de aprendizaje por refuerzo con algunas puntuaciones heurísticas calculadas con el algoritmo PageRank . ^{[ 7 ]}

Los algoritmos de subgrafos inducidos comunes máximos constituyen la base tanto de la diferenciación como de la alineación de grafos. La diferenciación de grafos identifica y resalta las diferencias entre dos grafos al detectar cambios, adiciones o eliminaciones. La alineación de grafos consiste en encontrar correspondencias entre los vértices y las aristas de dos grafos para identificar estructuras similares.

Los algoritmos de subgrafos inducidos comunes máximos tienen una larga tradición en bioinformática , quimioinformática , ^{[ 8 ] [ 9 ]} mapeo de farmacóforos , ^{[ 10 ]} reconocimiento de patrones , ^{[ 11 ]} visión por computadora , análisis de código, compiladores y verificación de modelos .

Este problema resulta especialmente útil en la ingeniería de software y la ingeniería de sistemas basada en modelos , donde el código de software y los modelos de ingeniería (por ejemplo, Simulink , diagramas UML ) se representan como estructuras de datos gráficas. La comparación de grafos permite detectar cambios entre distintas versiones de código y modelos de software para la auditoría de cambios, la depuración, el control de versiones y el desarrollo colaborativo en equipo.

• Minería molecular
• subgrafo de arista común máxima