A Reduction-Based Algorithm for the Clique Interdiction Problem
Authors: Chenghao Zhu, Yi Zhou, Haoyu Jiang
IJCAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Extensive experiments on 124 large realworld networks demonstrate the superior performance of RECIP and validate the effectiveness of the proposed reduction rules. |
| Researcher Affiliation | Academia | Chenghao Zhu , Yi Zhou , Haoyu Jiang University of Electronic Science and Technology of China EMAIL, EMAIL, First EMAIL |
| Pseudocode | Yes | Algorithm 1 RECIP Input: Graph G = (V, E), an integer k Output: θ(G, k) 1: G, k, lb, Cliques preprocess(G, k) 2: ans branc and cut(G, k, lb, Cliques) 3: return ans |
| Open Source Code | Yes | The source codes are publicly available 1. 1https://github.com/axs7385/RECIP |
| Open Datasets | Yes | Our experiments use 124 real-world networks sourced from the SNAP database and the Network Repository[Leskovec and Sosiˇc, 2014; Rossi and Ahmed, 2015] 2. The dataset covers a variety of categories, including social networks, technological networks, biological networks, and more. These graphs can be as large as 1.9 million vertices and 5 million edges. We leave a detailed description in the appended file. 2The dataset can be downloaded from https://lcs.ios.ac.cn/ caisw/graphs.html. |
| Dataset Splits | No | The paper investigates an optimization problem (Clique Interdiction Problem) on given graphs, not a machine learning task requiring train/test/validation splits. The 'budgets' mentioned (e.g., k = 0.005|V|) are parameters for the optimization problem itself, not data partitioning for model training or evaluation. |
| Hardware Specification | Yes | All experiments were conducted on a machine equipped with an AMD R9-7940HX CPU and 16GB of RAM, running Ubuntu 22.04. |
| Software Dependencies | Yes | The codes were written in C++ and compiled with GCC version 11.4.0 using the -O2 optimization flag. The IBM CPLEX solver version 12.7 was used as the underlying solver for the integer linear program. |
| Experiment Setup | Yes | We compare the performance of the two algorithms under four different budget values (k { 0.005|V | , 0.01|V | , 0.02|V | , 0.05|V | }) with a runtime limit of 600 seconds. |