---
title: "A Parallel Framework for the Maximum Common Induced Subgraph Problem"
authors:
  - "Jieyu Wu"
  - "Quan Zhang"
  - "Yiyuan Wang"
  - "Shiwei Pan"
  - "Jian Gao"
doi: "10.24963/ijcai.2026/709"
url: "https://ijcai.org/proceedings/2026/709"
pdf: "https://ijcai.org/proceedings/2026/0709.pdf"
venue: "Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"
year: 2026
pages: "6370-6378"
track: "Main Track"
keywords:
  - "Search: Heuristic search"
  - "Search: Combinatorial search and optimisation"
---

# A Parallel Framework for the Maximum Common Induced Subgraph Problem

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

*Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence*, pages 6370-6378. DOI: [10.24963/ijcai.2026/709](https://doi.org/10.24963/ijcai.2026/709)

## 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.