A Parallel Framework for the Maximum Common Induced Subgraph Problem

Wu, Jieyu; Zhang, Quan; Wang, Yiyuan; Pan, Shiwei; Gao, Jian

doi:10.24963/ijcai.2026/709

A Parallel Framework for the Maximum Common Induced Subgraph Problem

Jieyu Wu, Quan Zhang, Yiyuan Wang, Shiwei Pan, Jian Gao

Download BibTeX Cite

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence. Main Track. Pages 6370-6378.

https://doi.org/10.24963/ijcai.2026/709

Keywords

Search: Heuristic search
Search: Combinatorial search and optimisation

Abstract

Finding the maximum common induced subgraph (MCIS) between two graphs is a well-known NP-hard problem. While sequential MCIS algorithms have been extensively studied, parallel computing has emerged as an important direction for further performance enhancement with the advancement of computing resources. In this paper, we propose a parallel MCIS framework integrating a dynamic task decomposition method guided by search information and a novel pruning strategy based on shared information. The experimental results demonstrate that the algorithm enhanced by our framework achieves superior performance over both state-of-the-art sequential and existing parallel algorithms. Extensive results further demonstrate the wide scalability and generality of our framework, and the effectiveness of our strategies.

Jieyu Wu, Quan Zhang, Yiyuan Wang, Shiwei Pan, and Jian Gao. 2026. A Parallel Framework for the Maximum Common Induced Subgraph Problem. In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26. IJCAI, 6370–6378. https://doi.org/10.24963/ijcai.2026/709

@inproceedings{ijcai2026p709,
  title     = {A Parallel Framework for the Maximum Common Induced Subgraph Problem},
  author    = {Wu, Jieyu and Zhang, Quan and Wang, Yiyuan and Pan, Shiwei and Gao, Jian},
  booktitle = {Proceedings of the Thirty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-26}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Diego Calvanese},
  pages     = {6370--6378},
  year      = {2026},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2026/709},
  url       = {https://doi.org/10.24963/ijcai.2026/709},
}

TY  - CPAPER
TI  - A Parallel Framework for the Maximum Common Induced Subgraph Problem
AU  - Wu, Jieyu
AU  - Zhang, Quan
AU  - Wang, Yiyuan
AU  - Pan, Shiwei
AU  - Gao, Jian
T2  - Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2026
SP  - 6370
EP  - 6378
DO  - 10.24963/ijcai.2026/709
UR  - https://doi.org/10.24963/ijcai.2026/709
ER  -