The maximum common edge subgraph problem: A polyhedral investigation

In the Maximum Common Edge Subgraph Problem (MCES), given two graphs GG and HH with the same number of vertices, one has to find a common subgraph of GG and HH (not necessarily induced) with the maximum number of edges. This problem arises in parallel programming environments, and was first defined in Bokhari (1981) [2]. This paper presents a new integer programming formulation for the MCES and a polyhedral study of this model. Several classes of valid inequalities are identified, most of which are shown to define facets. These findings were incorporated into a branch&cut algorithm we implemented. Experimental results with this algorithm are reported.