Research map / Learning theory and algorithms / Combinatorial and search optimization
A Fast Exact Solver with Theoretical Analysis for the Maximum Edge-Weighted 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.
Proves MEWCP is NP-hard even when min degree is n-2, and presents MEWCat, a branch-and-bound exact solver with a tighter upper bound and O*(1.4423^n) worst-case time, outperforming BBEWC and MECQ.
Problem
Exact solving of the maximum edge-weighted clique problem (MEWCP), whose complexity on near-complete graphs differs from the vertex-weighted variant, and whose existing exact solvers lack worst-case guarantees better than O*(2^n).
Approach
Reduces the MEWCP subproblem to a vertex-and-edge-weighted clique problem and derives a tighter upper bound via independent set partitioning with ordered vertex-wise bounds, used in a GetBranches routine to prune branches; the search tree analysis yields O*(3^(n/3)).
Key results
- MEWCat solves all 16 DIMACS instances that BBEWC fails to solve within 7200 s, averaging under 1000 s.
- On real-world graphs MEWCat achieves an average speedup of over 36x versus MECQ and 47x versus BBEWC.
- Proves a worst-case running time bound of O*(1.4423^n) for MEWCat, breaking the trivial O*(2^n) bound of prior practical MEWCP solvers.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MEWCat instead of MECQ or BBEWC | MEWCP exact solving · real-world graphs | running time: over 36x faster than MECQ; over 47x faster than BBEWC | Helped |
| Use MEWCat instead of BBEWC | MEWCP exact solving · 16 DIMACS instances BBEWC fails to solve within 7200 seconds | solved instances: MEWCat solves all of them; average time of less than 1000 seconds | Helped |
| Use MEWCat's new upper bound in branch-and-bound | MEWCP exact solving · DIMACS graphs | tree size | Helped |
| Use MEWCat instead of the best of MECQ and BBEWC | MEWCP exact solving · random graphs | running time: 2.53; 2.31 | Helped |
Surprising findings
- MEWCP is NP-hard even when the minimum degree is n-2, whereas MVWCP is polynomial-time solvable at minimum degree n-3 or higher.
Limitations
- BBEWC source code was unavailable, so its reported times were scaled by a machine-speed factor for comparison.
- Experiments use a synthetic edge-weight assignment ((u+v) mod 200 + 1) rather than application-derived weights.
Experimental setup
Datasets: DIMACS graphs real-world graphs from Network Repository random graphs
Benchmarks: DIMACS graphs real-world graphs random graphs
Metrics: running time (seconds) search tree size
Baselines: BBEWC MECQ EWCLIQUE
Builds on: Tomita and Seki independent set partition bound PLS local search MECQ BBEWC
Closest papers by meaning
- KD-Club: An Efficient Exact Algorithm with New Coloring-Based Upper Bound for the Maximum k-Defective Clique Problem (AAAI 2024 · similarity 0.89)
- An Elite-guided Weighted Simulated Annealing Algorithm for the Clique Partitioning Problem (AAAI 2025 · similarity 0.88)
- Pre-Assignment Problem for Unique Minimum Vertex Cover on Bounded Clique-Width Graphs (AAAI 2025 · similarity 0.86)
- Optimal Quasi-clique: Hardness, Equivalence with Densest-k-Subgraph, and Quasi-partitioned Community Mining (AAAI 2024 · similarity 0.86)
- Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better (ICML 2024 · similarity 0.85)
- Differentiable Quadratic Optimization For the Maximum Independent Set Problem (ICML 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.