Research map / Learning theory and algorithms / Combinatorial and search optimization
KD-Club: An Efficient Exact Algorithm with New Coloring-Based Upper Bound for the Maximum k-Defective Clique Problem
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes CLUB, a graph-coloring-based upper bound for the maximum k-defective clique problem, and the KD-Club branch-and-bound algorithm that uses it for both preprocessing and pruning.
Problem
Exact solving of the Maximum k-Defective Clique Problem (MDCP), where branch-and-bound performance depends on how tight the upper bound on the size of a maximum k-defective clique is.
Approach
CLUB partitions candidate vertices by their missing edges to the partial solution, colors each group into independent sets, and uses the forced missing edges among vertices sharing an independent set to derive a tighter bound than KDBB, which treats the candidate set as a clique. CLUB is used both for graph reduction (Rules 3 and 4) and for branch pruning.
Key results
- On DIMACS2 with k=20, KD-Club solves 12 instances versus 11 for KDBB and 1 for MADEC+.
- On Facebook with k=20, KD-Club solves 104 instances versus 86 for KDBB and 0 for MADEC+.
- On Realworld with k=15, KD-Club solves 94 instances versus 70 for KDBB and 22 for MADEC+.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CLUB in both preprocessing and BnB search instead of the KDBB bounds (ablation) | KD-Club · MDCP instances across 341 graphs, k=3 and k=10 | number of instances solved over time | Helped |
| Use CLUB during preprocessing; retain KDBB-style BnB search (ablation) | KD-Club · MDCP instances, k=10 | number of instances solved over time | No clear effect |
| Use CLUB during BnB search; retain KDBB preprocessing (ablation) | KD-Club · MDCP instances with large k | number of instances solved over time | Helped |
| Replace KDBB's bound with coloring-based CLUB that accounts for missing edges among candidates | KDBB · MDCP | upper bound tightness | Helped |
Surprising findings
- MADEC+ solves almost no instances with k of 3 or more on the Facebook and Realworld benchmarks, far below its performance with k=1.
Limitations
- Preprocessing with CLUB is less effective as k grows, since fewer graph reductions are possible for large k.
- Coloring-based bound costs O(D|C|^2), which can be expensive on large-degree graphs.
Experimental setup
Datasets: Facebook socfb graphs Realworld graphs SNAP DIMACS10 DIMACS2
Benchmarks: Facebook Realworld SNAP and DIMACS10 DIMACS2
Metrics: number of solved instances within cut-off time running time search tree size
Baselines: KDBB MADEC+
Builds on: KDBB MADEC+ RDS
Closest papers by meaning
- A Fast Exact Solver with Theoretical Analysis for the Maximum Edge-Weighted Clique Problem (AAAI 2024 · similarity 0.89)
- Optimal Quasi-clique: Hardness, Equivalence with Densest-k-Subgraph, and Quasi-partitioned Community Mining (AAAI 2024 · similarity 0.88)
- Differentiable Quadratic Optimization For the Maximum Independent Set Problem (ICML 2025 · similarity 0.85)
- Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better (ICML 2024 · similarity 0.85)
- Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges (ICML 2025 · similarity 0.85)
- Densest k-Subgraph Mining via a Provably Tight Relaxation (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.