Parte de la dificultad de obtener más información sobre este problema es que el problema de coincidencia de gráficos es diferente de su primo mucho más famoso, el problema de coincidencia, pero es difícil distinguirlo cuando se utilizan motores de búsqueda.
Dados dos gráficos y modo que, la tarea es encontrar una biyección tal manera que esta biyección establezca tantas correspondencias entre los bordes de y como sea posible.
En otras palabras, si y son las matrices de adyacencia, entonces queremos maximizar
Este problema contiene claramente el isomorfismo gráfico como un caso especial, y puede reducirse a una coincidencia bipartita bajo una reducción (¡no polinomial!).
¿Qué tipo de algoritmos existen y qué se sabe sobre su complejidad?
El artículo que @Austin Buchanan señaló anteriormente sobre el isomorfismo gráfico aproximado no parece corresponder a la versión solicitada. Supongo que la matriz de adyacencia tiene entradas, en cuyo caso el objetivo es medir solo los bordes coincidentes. El modelo aproximado de isomorfismo gráfico mide tanto los bordes coincidentes como los no coincidentes, lo que lo hace un poco más fácil desde un punto de vista de aproximación.0,1
Parece que el problema planteado es al menos tan difícil como el problema del subgrafo denso que actualmente solo admite una aproximación polinómica. Consulte http://arxiv.org/abs/1001.2891 y http://arxiv.org/abs/1110.1360 para obtener más detalles y el estado actual en términos de algoritmos y dureza.k
Ahora para la reducción. Supongamos que queremos resolver el problema -densa-subgrafía en un gráfico ; es decir, queremos encontrar un subconjunto de nodos que maximice el número de aristas en el gráfico inducido . Puede reducir esto a su problema estableciendo sea un gráfico que consiste en un clique sobre -vertices y vértices aislados, y se fija para ser .k H k S G[S] G k n−k G′ H
fuente