Maximum common induced subgraph parameterized by vertex cover

Faisal Abu Khzam

Research output: Contribution to journalArticlepeer-review

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 arameterization
problems is Vertex Cover. In this paper we prove constructively that MCIS is fixedparameter 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.
Original languageEnglish
Pages (from-to)99-103
Number of pages5
JournalInformation Processing Letters
Volume114
Issue number3
DOIs
Publication statusPublished - Mar 2014
Externally publishedYes

Fingerprint

Dive into the research topics of 'Maximum common induced subgraph parameterized by vertex cover'. Together they form a unique fingerprint.

Cite this