Improving Upper Bounds for the Maximum Clique Problem using Reduction Rules
We study the interaction between reduction rules and upper-bound functions for the Maximum Clique Problem (MCP). We show how MCP upper-bound functions can strengthen classical core and truss reductions by replacing local size conditions with upper-bound tests. This leads to the \((k,ω^u)\)-core, the \((k,ω^u)\)-truss, and the more general \((k,d,ω^u)\)-truss, where the parameter \(d\) controls the trade-off between stronger reductions and additional computational cost. For each of these notions, we prove clique-preservation properties, correctness of the corresponding peeling algorithm, and…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.11726
curl -X POST /api/v1/records/arxiv/2607.11726/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.11726/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'