{"id":"arxiv/2607.11726","url":"https://arxiv.org/abs/2607.11726","tags":["math.CO","cs.DS"],"score":0,"title":"Improving Upper Bounds for the Maximum Clique Problem using Reduction Rules","domain":"math.CO","source":"arxiv","authors":["Aljaž Krpan","Janez Povh"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-13","reactions":{}}