Maximum common induced subgraph parameterized by vertex cover

Abstract

The Maximum Common Induced Subgraph problem (MCIS ) takes a pair of graphs as input and asks for a graph of maximum order that is isomorphic to an induced subgraph of each of the input graphs. The problem is NP-hard in general, and remains so on many graph classes including graphs of bounded treewidth. In the framework of parameterized complexity, the latter assertion means that MCIS is W[1]-hard when parameterized by the treewidths of input graphs.

A classical graph parameter that has been used recently in many parameterization problems is Vertex Cover. In this paper we prove constructively that MCIS is fixed-parameter tractable when parameterized by the vertex cover numbers of the input graphs. Our algorithm is also an improved exact algorithm for the problem on instances where the minimum vertex cover is small compared to the order of input graphs.