This paper presents some strong valid inequalities for the Maximum Common Induced Subgraph Problem (MCIS) and the proofs that the inequalities are facet-defining under certain conditions. The MCIS is an NP-hard problem and, therefore, no polynomial time algorithm is known to solve it. In this context, the study of its polytope can help in the development of more efficient branch-and-bound and branch-and-cut algorithms.
Article
View Facets for the Maximum Common Induced Subgraph Problem Polytope