Maximum common edge subgraph

<p>Given two <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graphs</a> 
  
    
      
        G
      
    
    {\displaystyle G}
  
 and 
  
    
      
        
          G
          ′
        
      
    
    {\displaystyle G'}
  
, the maximum common edge subgraph problem is the problem of finding a graph 
  
    
      
        H
      
    
    {\displaystyle H}
  
 with as many  edges as possible which is <a href="/facts/Graph_isomorphism/SBjVIhwW">isomorphic</a> to both a <a href="/facts/Glossary_of_graph_theory/W0MqKkyE">subgraph</a> of 
  
    
      
        G
      
    
    {\displaystyle G}
  
 and a subgraph of 
  
    
      
        
          G
          ′
        
      
    
    {\displaystyle G'}
  
.
</p><p>The maximum common edge subgraph problem on general graphs is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a> as it is a generalization of <a href="/facts/Subgraph_isomorphism/86LLWRg4">subgraph isomorphism</a>: a graph 
  
    
      
        H
      
    
    {\displaystyle H}
  
 is isomorphic to a subgraph of another graph 
  
    
      
        G
      
    
    {\displaystyle G}
  
 if and only if the maximum common edge subgraph of 
  
    
      
        G
      
    
    {\displaystyle G}
  
 and 
  
    
      
        H
      
    
    {\displaystyle H}
  
 has the same number of edges as 
  
    
      
        H
      
    
    {\displaystyle H}
  
. The problem is <a href="/facts/APX-hard/ggqAJ3A3">APX-hard</a>, unless the two input graphs 
  
    
      
        G
      
    
    {\displaystyle G}
  
 and 
  
    
      
        
          G
          ′
        
      
    
    {\displaystyle G'}
  
 are required to have the same number of vertices.
</p>

Maximum common edge subgraph open-in-new

Maximum common edge subgraph