Common Induced Subgraph Isomorphism: Structural Parameterizations and Exact Algorithms

Project Description: 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. MCIS has applications in a wide range of scientific domains, such as Bioinformatics, Chemistry, and Pattern Recognition. In this project, we study various structural parameterizations of the MCIS problem. MCIS is at least W[1]-hard in general and remains W[1]-hard when parameterized by the treewidth of input graphs. We study the possible use of some exact algorithms in some application domains by exploring graph classes and parameterization where the problem becomes fixed-parameter tractable.

PI: Faisal N. Abu-Khzam

Funding: This project has been partially funded by the Lebanese American University.

Publications:

F. N. Abu-Khzam, E. Bonnet and F. Sikora. On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism. Theoretical Computer Science (Elsevier), volume 697, pages 69-78, 2017.

F. N. Abu-Khzam, E. Bonnet and F. Sikora. On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism, in Proceedings of the 25th International Workshop on Combinatorial Algorithms (IWOCA 2014), Lecture Notes in Computer Science, volume 8986, pages 1-12, 2014

F. N. Abu-Khzam. Maximum Common Induced Subgraph Parameterized by Vertex Cover, Information Processing Letters, volume 114, number 3, pages 99-103, 2014.

Previous publications (from related older projects):

F. N. Abu-Khzam, M. A. Rizk, N. F. Samatova and M. A. Langston. The Maximum Common Subgraph Problem: Faster Solutions via Vertex Cover, in Proceedings, ACS/IEEE International Conference on Computer Systems and Application (AICCSA 2007): pages 367-373, 2007.

W. H. Suters, F. N. Abu-Khzam, Y. Zhang, C. T. Symons, N. F. Samatova and M. A. Langston. A New Approach and Faster Exact Methods for the Maximum Common Subgraph Problem, in Proceedings of the 11th International Computing and Combinatorics Conference (COCOON 2005), Lecture Notes in Computer Science, volume 3595, pages 717-727, 2005.