A Reduction-Based Algorithm for the Clique Interdiction Problem

Zhu, Chenghao; Zhou, Yi; Jiang, Haoyu

doi:10.24963/ijcai.2025/1003

A Reduction-Based Algorithm for the Clique Interdiction Problem

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 9022-9030.

https://doi.org/10.24963/ijcai.2025/1003

Keywords

Search: S: Combinatorial search and optimisation
Search: S: Mixed discrete/continuous search
Search: S: Heuristic search

Abstract

The Clique Interdiction Problem (CIP) aims to minimize the size of the largest clique in a given graph by removing a given number of vertices.

The CIP models a special Stackelberg game and has important applications in fields such as pandemic control and terrorist identification.

However, the CIP is a bilevel graph optimization problem, making it very challenging to solve. Recently, data reduction techniques have been successfully applied in many (single-level) graph optimization problems like vertex cover.

Motivated by this, we investigate a set of novel reduction rules and design a reduction-based algorithm, RECIP, for practically solving the CIP.

RECIP enjoys an effective preprocessing procedure that systematically reduces the input graph, making the problem much easier to solve.

Extensive experiments on 124 large real-world networks demonstrate the superior performance of RECIP and validate the effectiveness of the proposed reduction rules.

Chenghao Zhu, Yi Zhou, and Haoyu Jiang. 2025. A Reduction-Based Algorithm for the Clique Interdiction Problem. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 9022–9030. https://doi.org/10.24963/ijcai.2025/1003

@inproceedings{ijcai2025p1003,
  title     = {A Reduction-Based Algorithm for the Clique Interdiction Problem},
  author    = {Zhu, Chenghao and Zhou, Yi and Jiang, Haoyu},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {9022--9030},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/1003},
  url       = {https://doi.org/10.24963/ijcai.2025/1003},
}

TY  - CPAPER
TI  - A Reduction-Based Algorithm for the Clique Interdiction Problem
AU  - Zhu, Chenghao
AU  - Zhou, Yi
AU  - Jiang, Haoyu
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 9022
EP  - 9030
DO  - 10.24963/ijcai.2025/1003
UR  - https://doi.org/10.24963/ijcai.2025/1003
ER  -