Subgrafo de arista común máxima

Dados dos gráficos y , el problema del subgrafo de máxima arista común es el problema de encontrar un gráfico con tantas aristas como sea posible que sea isomorfo tanto a un subgrafo de como a un subgrafo de . ${\displaystyle G}$ ${\displaystyle G'}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle G'}$

El problema del subgrafo de máxima arista común en grafos generales es NP-completo ya que es una generalización del isomorfismo de subgrafos : un grafo es isomorfo a un subgrafo de otro grafo si y solo si el subgrafo de máxima arista común de y tiene el mismo número de aristas que . A menos que se requiera que las dos entradas y al problema del subgrafo de máxima arista común tengan el mismo número de vértices, el problema es APX-duro . ^[1] ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle G'}$

Véase también

• Problema de isomorfismo del subgrafo común máximo
• Problema de isomorfismo de subgrafos
• Problema de isomorfismo de subgrafos inducidos

Referencias

1. Bahiense, L.; Manic, G.; Piva, B.; de Souza, CC (2012), "El problema del subgrafo de máxima arista común: una investigación poliédrica", Discrete Applied Mathematics , 160 (18): 2523–2541, doi : 10.1016/j.dam.2012.01.026.