Strength of the Upper Bounds for the Edge-Weighted Maximum Clique Problem

Fabio Ciccarelli; Fabio Furini; Marta Monaci; Valerio Dose

arxiv: 2507.06898 · v2 · submitted 2025-07-09 · 🧮 math.OC · math.CO

Strength of the Upper Bounds for the Edge-Weighted Maximum Clique Problem

Fabio Ciccarelli , Valerio Dose , Fabio Furini , Marta Monaci This is my paper

Pith reviewed 2026-05-19 05:58 UTC · model grok-4.3

classification 🧮 math.OC math.CO

keywords edge-weighted maximum cliqueupper boundsunbounded ratiosperformance guaranteesrelative strengthcombinatorial optimizationDIMACS instances

0 comments

The pith

None of the three main upper bounds for the edge-weighted maximum clique problem can guarantee a bounded ratio to the optimum.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper compares the three primary upper bounds from the literature for the edge-weighted maximum clique problem. It constructs families of graphs where each bound overestimates the optimal value by an arbitrarily large factor, proving that none delivers a performance guarantee. The analysis further shows that any desired ratio between any pair of bounds can be achieved on suitably chosen instances, so that each bound can be the tighter one depending on the graph. These theoretical results are checked through computational tests on DIMACS benchmarks and random graphs.

Core claim

For each of the three upper bounds there exist instance families making the ratio to the optimal EWMCP value unbounded. For every pair of bounds the maximum attainable ratio is determined and realized by explicit families of graphs, showing that the bounds are incomparable in strength.

What carries the argument

Families of specially constructed graphs that force each upper bound to diverge unboundedly from the optimal weighted-clique value.

If this is right

No single upper bound supplies a worst-case guarantee when used inside branch-and-bound or similar solvers for EWMCP.
Which bound performs best depends on the structure of the particular graph instance.
Practical solvers must test multiple bounds or combine them rather than relying on one.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar constructions could reveal whether unbounded ratios appear in related problems such as weighted independent set.
An algorithm that dynamically selects among the three bounds might improve average-case performance even if none is universally best.
The results point to the need for new relaxation techniques that achieve bounded ratios on at least some nontrivial graph classes.

Load-bearing premise

The graph families constructed in the paper truly make each upper bound arbitrarily larger than the optimal clique weight.

What would settle it

A calculation on one of the constructed families that keeps the ratio between some upper bound and the optimal value below a fixed constant no matter how large the family parameter grows.

Figures

Figures reproduced from arXiv: 2507.06898 by Fabio Ciccarelli, Fabio Furini, Marta Monaci, Valerio Dose.

**Figure 2.** Figure 2: The values of the two upper bounds UB1(G, c, C ) and UB2(G, c, C ) for the instances in [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** Figure 3: Representation of the graph G1 n , where the vertices are colored using the minimum number of colors. Each vertex is labeled with a natural number displayed inside the node. The two ellipses represent the cliques C1 and C2. The edge-weight c¯ of each edge connecting a vertex in C1 to a vertex in C2 is shown next to the edge. All edges within each clique have weight one; these values are omitted from the fi… view at source ↗

**Figure 4.** Figure 4: Representation of the graph G2 3 , where the vertices are colored using the minimum number of colors. Each vertex is labeled with a natural number displayed inside the node. The edge-weights are shown next to the corresponding edges. 0 0 0 1 0 1 1 1 0 1 1 0 1 2 3 4 5 6 7 8 9 vertex u and one vertex for every set Cv with v ≠ u, which has not been included in an independent set yet. By construction, every e… view at source ↗

**Figure 5.** Figure 5: Representation of the graph G3 n , where the vertices are colored using the minimum number of colors. Each vertex is labeled with a natural number displayed inside the node. All edge-weights are equal to 1; these values are omitted from the figure. 1 2 . . . n n + 1 n + 2 . . . 2 n The following proposition states that the ratio between the upper bound UB1(G, c, C ) and UB2(G, c, C ) can be arbitrarily lar… view at source ↗

**Figure 6.** Figure 6: Box plot representation of the percentage gap of the two upper bounds on RANDOM [PITH_FULL_IMAGE:figures/full_fig_p022_6.png] view at source ↗

**Figure 7.** Figure 7: Box plot representation of the percentage gap of the two upper bound on RANDOM instances [PITH_FULL_IMAGE:figures/full_fig_p023_7.png] view at source ↗

**Figure 8.** Figure 8: Box plot representation of the percentage difference of the two upper bounds on RANDOM [PITH_FULL_IMAGE:figures/full_fig_p024_8.png] view at source ↗

**Figure 9.** Figure 9: Box plot representation of the percentage difference of the two upper bounds on RANDOM [PITH_FULL_IMAGE:figures/full_fig_p025_9.png] view at source ↗

read the original abstract

We theoretically and computationally compare the strength of the three main upper bounds from the literature on the optimal value of the Edge-Weighted Maximum Clique Problem (EWMCP). We provide a set of instances for which the ratio between any of the three upper bounds and the optimal value of the EWMCP is unbounded, showing that none of them can give a performance guarantee. We further analyze the relative strength among the three upper bounds by determining, for every choice of a ratio between any two of them, the largest values it can attain and providing families of instances for which such values can be reached. Our results show that, for each pair of upper bounds, there exist appropriately chosen instances on which either bound is tighter than the other. Our theoretical analysis is complemented by extensive computational experiments on two benchmark datasets: the standard DIMACS instances and randomly generated instances, providing practical insights into the empirical strength of the upper bounds.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper builds explicit instance families proving unbounded ratios to OPT for each of the three standard upper bounds on the edge-weighted max clique and maps the pairwise relative strengths between them.

read the letter

This paper shows that none of the three main upper bounds for the edge-weighted maximum clique can have a bounded ratio to the optimum, using new families of instances, and it also determines the relative strengths between each pair of bounds with additional families. What stands out is the explicit constructions. They create graphs where the optimum stays small, like a single edge with fixed weight, while each bound grows without limit as a parameter increases. They prove this for each bound in turn. For the comparisons they find the maximum ratio one bound can have over another and show instances that reach it. The experiments on standard DIMACS instances and random graphs add some practical perspective on which bound performs better on average. The work does a good job of ruling out performance guarantees from these bounds and giving a clear picture of when one is better than the others. The theoretical part is the core contribution here. The main soft spot is that the unbounded results depend on the precise definitions and the way the instances are weighted and structured. If the optima are indeed as claimed in the limit, it works, but any slip in the calculations would affect the conclusion. The computational tests are straightforward and don't introduce new methods. This paper is for combinatorial optimizers focused on clique problems or bound tightening in integer programs. A reader looking for limitations of existing bounds or ideas for new ones would get something from the families. I recommend sending it for peer review. The claims are concrete and the evidence is a mix of proofs and experiments, so it deserves a look from referees who can verify the constructions.

Referee Report

3 major / 2 minor

Summary. The paper compares the strength of three main upper bounds from the literature for the Edge-Weighted Maximum Clique Problem (EWMCP). It constructs families of instances showing that for each bound the ratio to the true optimum is unbounded, implying none provides a performance guarantee. It further determines the supremum of the ratio between every pair of bounds and exhibits instance families attaining these values in both directions. The theoretical analysis is complemented by computational experiments on DIMACS benchmark graphs and randomly generated instances.

Significance. If the instance constructions and ratio calculations hold, the results establish that existing upper bounds for EWMCP lack worst-case guarantees and that their relative tightness is instance-dependent. This provides concrete guidance for selecting or combining bounds in branch-and-bound algorithms and highlights the need for stronger bounding techniques in edge-weighted clique problems.

major comments (3)

[§4.1] §4.1 (unbounded ratio for bound U1): The construction claims that OPT remains constant while U1 grows linearly with parameter k, but the argument that no larger clique can achieve higher total weight relies on an implicit non-negativity assumption on edge weights that is not stated in the bound definition; an explicit verification that all other potential cliques have weight at most 1 is required.
[§4.3] §4.3, Theorem 3: The family showing that the ratio U2/U3 can be arbitrarily large uses a specific weight assignment; however, the exact evaluation of U3 on this family appears to omit the contribution of the added high-weight edges that are present in the graph but outside the designated clique, which could cap the ratio.
[Table 2] Table 2 (computational results on random instances): The reported average gaps for the three bounds are presented without standard deviations or instance-size stratification; given that the theoretical claims concern asymptotic behavior, the empirical section should include scaling plots or results for n up to several hundred to support the practical relevance of the unbounded-ratio families.

minor comments (2)

[§2] Notation for the three bounds is introduced in §2 but the symbols U1, U2, U3 are not consistently used in the theorems of §4; uniform notation would improve readability.
[Abstract] The abstract states that 'for every choice of a ratio between any two of them, the largest values it can attain' are determined, yet the text only exhibits families achieving large ratios without proving that the exhibited values are indeed the suprema; a short remark clarifying whether the constructions are tight would help.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful and constructive review of our manuscript. We address each major comment below and indicate the revisions planned for the next version.

read point-by-point responses

Referee: [§4.1] §4.1 (unbounded ratio for bound U1): The construction claims that OPT remains constant while U1 grows linearly with parameter k, but the argument that no larger clique can achieve higher total weight relies on an implicit non-negativity assumption on edge weights that is not stated in the bound definition; an explicit verification that all other potential cliques have weight at most 1 is required.

Authors: We agree that the non-negativity assumption should be stated explicitly. The construction in §4.1 assumes non-negative edge weights, as is standard for the EWMCP. In the revised manuscript we will add an explicit statement of this assumption in the bound definition and provide a direct verification that every clique not contained in the designated structure has total weight at most 1, confirming that OPT equals 1 while U1 grows linearly with k. revision: yes
Referee: [§4.3] §4.3, Theorem 3: The family showing that the ratio U2/U3 can be arbitrarily large uses a specific weight assignment; however, the exact evaluation of U3 on this family appears to omit the contribution of the added high-weight edges that are present in the graph but outside the designated clique, which could cap the ratio.

Authors: We thank the referee for raising this point. Upon re-checking the construction, the added high-weight edges outside the designated clique do not increase the value of U3 because U3 is defined as the maximum clique weight and no larger clique can be formed that incorporates those edges while respecting the weight assignment. We will expand the proof of Theorem 3 with an explicit calculation of U3 on the family to make this transparent and to confirm that the ratio U2/U3 is indeed unbounded. revision: partial
Referee: [Table 2] Table 2 (computational results on random instances): The reported average gaps for the three bounds are presented without standard deviations or instance-size stratification; given that the theoretical claims concern asymptotic behavior, the empirical section should include scaling plots or results for n up to several hundred to support the practical relevance of the unbounded-ratio families.

Authors: We agree that the empirical section can be strengthened. In the revised manuscript we will augment Table 2 with standard deviations, stratify the reported gaps by instance size, and add scaling plots for randomly generated instances with n up to 500. These additional results have already been computed and will be included to better illustrate the asymptotic behavior observed in the theoretical constructions. revision: yes

Circularity Check

0 steps flagged

No circularity: explicit instance constructions and literature bounds evaluated directly

full rationale

The paper constructs explicit parameterized families of graphs and edge weights to demonstrate that each of the three literature upper bounds can have unbounded ratio to the EWMCP optimum, and similarly shows that for any pair of bounds either can be tighter on suitable instances. These results follow from direct substitution of the constructed instances into the bound formulas and identification of the optimum (typically a single edge or small clique), without any reduction of a derived quantity back to a fitted parameter, self-definition, or load-bearing self-citation. The bounds are referenced from prior literature rather than redefined in terms of the target results, and the computational experiments on DIMACS and random instances are separate empirical checks. The derivation chain is therefore self-contained and externally verifiable.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The paper relies on standard definitions of the EWMCP and three existing upper bounds from the literature; no new free parameters, axioms, or invented entities are introduced.

pith-pipeline@v0.9.0 · 5690 in / 893 out tokens · 29665 ms · 2026-05-19T05:58:33.356058+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We provide a set of instances for which the ratio between any of the two upper bounds and the optimal value of the EWMCP is unbounded... families of instances for which such values can be reached.
IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

U B1(G, c, C) := min ... dual of the LP relaxation... U B2(G, c, C) := sum max sigma_u

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

[1]

L. A. Agapito, M. Fornari, D. Ceresoli, A. Ferretti, S. Curtarolo, and M. B. Nardelli. Accurate tight-binding hamiltonians for two-dimensional and layered materials. Physical Review B, 93(12):125137, 2016

work page 2016
[2]

Br´ elaz

D. Br´ elaz. New methods to color the vertices of a graph. Communications of the ACM, 22(4):251–256, 1979

work page 1979
[3]

Coniglio, F

S. Coniglio, F. Furini, and P. San Segundo. A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts. European Journal of Operational Research, 289(2):435–455, 2021

work page 2021
[4]

Cornaz, F

D. Cornaz, F. Furini, and E. Malaguti. Solving vertex coloring problems as maximum weight stable set problems. Discrete Applied Mathematics, 217:151–162, 2017

work page 2017
[5]

Delle Donne, F

D. Delle Donne, F. Furini, E. Malaguti, and R. Wolfler Calvo. A branch-and-price algorithm for the minimum sum coloring problem. Discrete Applied Mathematics, 303:39–56, 2021

work page 2021
[6]

2nd dimacs implementation challenge – NP-Hard Problems: Maximum clique, graph coloring, and satisfiability

DIMACS. 2nd dimacs implementation challenge – NP-Hard Problems: Maximum clique, graph coloring, and satisfiability. http://archive.dimacs.rutgers.edu/ Challenges/, 2017

work page 2017
[7]

Furini, I

F. Furini, I. Ljubi´ c, S. Martin, and P. San Segundo. The maximum clique interdiction problem. European Journal of Operational Research, 277(1):112–127, 2019

work page 2019
[8]

Furini, I

F. Furini, I. Ljubi´ c, P. San Segundo, and Y. Zhao. A branch-and-cut algorithm for the edge interdiction clique problem. European Journal of Operational Research, 294(1):54–69, 2021

work page 2021
[9]

M. R. Gary and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. WH Freeman and Company, 1979

work page 1979
[10]

Gouveia and P

L. Gouveia and P. Martins. Solving the maximum edge-weight clique problem in sparse graphs with compact formulations. EURO Journal on Computational Optimization, 3(1):1–30, 2015

work page 2015
[11]

Hosseinian, D

S. Hosseinian, D. B. M. M. Fontes, and S. Butenko. A nonconvex quadratic optimization approach to the maximum edge weight clique problem. Journal of Global Optimization, 72:219–240, 2018. 26

work page 2018
[12]

R. M. Karp. Reducibility among combinatorial problems. In 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art , pages 219–241. Springer, 2010

work page 1958
[13]

T. L. Lei and R. L. Church. On the unified dispersion problem: Efficient formulations and exact algorithms. European Journal of Operational Research, 241(3):622–630, 2015

work page 2015
[14]

Ma and L

T. Ma and L. J. Latecki. Maximum weight cliques with mutex constraints for video object segmentation. In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 670–677, 2012

work page 2012
[15]

S. Mattia. Reformulations and complexity of the clique interdiction problem by graph mapping. Discrete Applied Mathematics, 354:48–57, 2024

work page 2024
[16]

O. A. Prokopyev, N. Kong, and D. L. Martinez-Torres. The equitable dispersion problem. European Journal of Operational Research, 197(1):59–67, 2009

work page 2009
[17]

San Segundo and J

P. San Segundo and J. Artieda. A novel clique formulation for the visual feature matching problem. Applied Intelligence, 43:325–342, 2015

work page 2015
[18]

San Segundo, F

P. San Segundo, F. Matia, D. Rodriguez-Losada, and M. Hernando. An improved bit parallel exact maximum clique algorithm. Optimization Letters, 7(3):467–479, 2013

work page 2013
[19]

San Segundo, S

P. San Segundo, S. Coniglio, F. Furini, and I. Ljubi´ c. A new branch-and-bound algorithm for the maximum edge-weighted clique problem. European Journal of Operational Research, 278(1):76–90, 2019

work page 2019
[20]

San Segundo, F

P. San Segundo, F. Furini, and J. Artieda. A new branch-and-bound algorithm for the maximum weighted clique problem. Computers & Operations Research, 110: 18–33, 2019

work page 2019
[21]

Shimizu, K

S. Shimizu, K. Yamaguchi, and S. Masuda. A branch-and-bound based exact algorithm for the maximum edge-weight clique problem. In Computational Sci- ence/Intelligence & Applied Informatics , pages 27–47. Springer, 2019

work page 2019
[22]

Shimizu, K

S. Shimizu, K. Yamaguchi, and S. Masuda. A maximum edge-weight clique extraction algorithm based on branch-and-bound. Discrete Optimization, 37:100– 583, 2020. 27

work page 2020

[1] [1]

L. A. Agapito, M. Fornari, D. Ceresoli, A. Ferretti, S. Curtarolo, and M. B. Nardelli. Accurate tight-binding hamiltonians for two-dimensional and layered materials. Physical Review B, 93(12):125137, 2016

work page 2016

[2] [2]

Br´ elaz

D. Br´ elaz. New methods to color the vertices of a graph. Communications of the ACM, 22(4):251–256, 1979

work page 1979

[3] [3]

Coniglio, F

S. Coniglio, F. Furini, and P. San Segundo. A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts. European Journal of Operational Research, 289(2):435–455, 2021

work page 2021

[4] [4]

Cornaz, F

D. Cornaz, F. Furini, and E. Malaguti. Solving vertex coloring problems as maximum weight stable set problems. Discrete Applied Mathematics, 217:151–162, 2017

work page 2017

[5] [5]

Delle Donne, F

D. Delle Donne, F. Furini, E. Malaguti, and R. Wolfler Calvo. A branch-and-price algorithm for the minimum sum coloring problem. Discrete Applied Mathematics, 303:39–56, 2021

work page 2021

[6] [6]

2nd dimacs implementation challenge – NP-Hard Problems: Maximum clique, graph coloring, and satisfiability

DIMACS. 2nd dimacs implementation challenge – NP-Hard Problems: Maximum clique, graph coloring, and satisfiability. http://archive.dimacs.rutgers.edu/ Challenges/, 2017

work page 2017

[7] [7]

Furini, I

F. Furini, I. Ljubi´ c, S. Martin, and P. San Segundo. The maximum clique interdiction problem. European Journal of Operational Research, 277(1):112–127, 2019

work page 2019

[8] [8]

Furini, I

F. Furini, I. Ljubi´ c, P. San Segundo, and Y. Zhao. A branch-and-cut algorithm for the edge interdiction clique problem. European Journal of Operational Research, 294(1):54–69, 2021

work page 2021

[9] [9]

M. R. Gary and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. WH Freeman and Company, 1979

work page 1979

[10] [10]

Gouveia and P

L. Gouveia and P. Martins. Solving the maximum edge-weight clique problem in sparse graphs with compact formulations. EURO Journal on Computational Optimization, 3(1):1–30, 2015

work page 2015

[11] [11]

Hosseinian, D

S. Hosseinian, D. B. M. M. Fontes, and S. Butenko. A nonconvex quadratic optimization approach to the maximum edge weight clique problem. Journal of Global Optimization, 72:219–240, 2018. 26

work page 2018

[12] [12]

R. M. Karp. Reducibility among combinatorial problems. In 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art , pages 219–241. Springer, 2010

work page 1958

[13] [13]

T. L. Lei and R. L. Church. On the unified dispersion problem: Efficient formulations and exact algorithms. European Journal of Operational Research, 241(3):622–630, 2015

work page 2015

[14] [14]

Ma and L

T. Ma and L. J. Latecki. Maximum weight cliques with mutex constraints for video object segmentation. In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 670–677, 2012

work page 2012

[15] [15]

S. Mattia. Reformulations and complexity of the clique interdiction problem by graph mapping. Discrete Applied Mathematics, 354:48–57, 2024

work page 2024

[16] [16]

O. A. Prokopyev, N. Kong, and D. L. Martinez-Torres. The equitable dispersion problem. European Journal of Operational Research, 197(1):59–67, 2009

work page 2009

[17] [17]

San Segundo and J

P. San Segundo and J. Artieda. A novel clique formulation for the visual feature matching problem. Applied Intelligence, 43:325–342, 2015

work page 2015

[18] [18]

San Segundo, F

P. San Segundo, F. Matia, D. Rodriguez-Losada, and M. Hernando. An improved bit parallel exact maximum clique algorithm. Optimization Letters, 7(3):467–479, 2013

work page 2013

[19] [19]

San Segundo, S

P. San Segundo, S. Coniglio, F. Furini, and I. Ljubi´ c. A new branch-and-bound algorithm for the maximum edge-weighted clique problem. European Journal of Operational Research, 278(1):76–90, 2019

work page 2019

[20] [20]

San Segundo, F

P. San Segundo, F. Furini, and J. Artieda. A new branch-and-bound algorithm for the maximum weighted clique problem. Computers & Operations Research, 110: 18–33, 2019

work page 2019

[21] [21]

Shimizu, K

S. Shimizu, K. Yamaguchi, and S. Masuda. A branch-and-bound based exact algorithm for the maximum edge-weight clique problem. In Computational Sci- ence/Intelligence & Applied Informatics , pages 27–47. Springer, 2019

work page 2019

[22] [22]

Shimizu, K

S. Shimizu, K. Yamaguchi, and S. Masuda. A maximum edge-weight clique extraction algorithm based on branch-and-bound. Discrete Optimization, 37:100– 583, 2020. 27

work page 2020