On the largest common subgraph problem

Abstract

Given two graphs G 1 = <V1, E1> and G 2 = <V2, E2>, |V 1I = IV 2| = n, to determine whether they have a size-k common subgraph is one of the earliest examples of an NP-complete problem (by a trivial reduction from the Maximum Clique problem). We show that this problem for equally sized G 1 and G 2, i.e. when IE 1I = IE 2I = m, remains NP-complete.