ULE-MWC: An UnLocking-Enhanced Lookahead Framework for Exact Maximum Weight Clique Search

1 Introduction

Given an undirected simple graph G = (V, E), where V denotes the vertex set and E is the edge set, a clique is a subset of vertices such that every pair of vertices is adjacent in G. The Maximum Clique Problem (MCP) aims to find a clique of maximum size in G. The Maximum Weight Clique Problem (MWCP) extends MCP by assigning each vertex v a nonnegative weight w(v), and seeks a clique C that maximizes the total weight w(C) = ∑v∈C w(v). In this paper, we focus on algorithms for solving MWCP.

MCP is a classical NP-hard problem [Hartmanis, 1982]. Since MCP is a special case of MWCP where all vertex weights are equal to 1, MWCP is also NP-hard. Due to its theoretical importance and practical value, MWCP has been applied in many areas, including coding theory [Zhian et al., 2013], computer vision [Zhang et al., 2014; Sanroma et al., 2016], protein structure prediction [Mascia et al., 2010], and genomics [Butenko and Wilhelm, 2006].

∗Corresponding author.

A large range of algorithms have been proposed for MWCP, which are generally divided into two categories: heuristics and exact methods. The most efficient heuristic algorithms include MN/TS [Wu et al., 2012], FastWClq [Cai and Lin, 2016], RRWL [Fan et al., 2017], ReTS [Zhou et al., 2017], and SCCWalk [Wang et al., 2020]. And representative exact methods include Cliquer [ ¨Osterg˚ard, 2002], MWCLQ [Fang et al., 2016], WLMC [Jiang et al., 2017], TSMMWC [Jiang et al., 2018], and BBMWC [San Segundo et al., 2019], most of which are based on the Branch-and-Bound (BnB) framework.

A BnB algorithm for MWCP usually maintains a growing partial clique S and a corresponding candidate set P . Vertices in P are adjacent to all vertices in S, so adding any vertex from P to S keeps S a clique. Let ω(G, w) denote the weight of the best clique found so far in G. If an upper bound on the maximum weight clique that can be obtained on the current search node is no greater than ω(G,w), the branch can be safely pruned. Therefore, the quality of the upper bounds plays a crucial role in reducing the search space and improving the efficiency of the algorithms.

MaxSAT reasoning is an effective way to improve the upper bounds. It was developed for MCP [Li and Quan, 2010; Li et al., 2017; Li et al., 2018], and has recently been extended to MWCP [Jiang et al., 2017; Jiang et al., 2018]. Starting from an independent set based upper bound, MaxSAT reasoning formulates the clique problem as a partial MaxSAT instance and further improves the bound by identifying conflicts, i.e., groups of independent sets whose vertices cannot be selected to form a clique simultaneously.

Though MWCP solvers based on MaxSAT reasoning have achieved strong pruning performance, there are still several limitations. Once a conflict is identified, existing methods compute its conflicting weight, split the involved independent sets, and permanently remove the conflicting parts, which prevents the reuse of potentially valuable independent sets in later reasoning. Besides, conflicts are encountered in a fixed order, and the bound reduction is dominated by lowweight independent sets in it. Thus, a conflict often provides

Algorithm 1: BnB(G, P, O, S, C ∗ )

Input: G = (V, E, w), a vertex ordering O over V , the growing clique S, the candidate set P, and the maximum weight clique C ∗ found so far. Output: The maximum weight clique C ∗ 1 if |P| = 0 then return S; 2 B ←GetBranches(G[P],w(C ∗ ) -w(S),O); 3 if B = ∅ then return C ∗ ; 4 Let B = {b1, b2, · · · , b|B|} w.r.t. O and A ← P \ B; 5 for i = |B| to 1 do 6 P ′ =N(bi) ∩ ({bi+1, · · · , b|B|} ∪A); 7 C ′ ←BnB(G, P ′ ,O, S ∪ {bi},C ∗ ); 8 if w(C ′ ) > w(C ∗ ) then C ∗ ← C ′ ; 9 return C ∗ ;

minor bound reductions while still requiring the full cost of MaxSAT reasoning. Consequently, the pruning gain is not always proportional to the computational effort.

To address these limitations, we introduce two complementary strategies. The UnLocking Mechanism (ULM) preserves conflict cores by temporarily locking them, which allows the associated independent sets to participate in later reasoning. The Benefit-Enhanced Strategy (BES) guides the reasoning process by filtering independent sets to detect conflicts with higher pruning potential. We introduce ULM and BES into the MaxSAT reasoning process and develop the ULE-MWC solver. Extensive experiment results show that ULE-MWC consistently produces tighter bounds and achieves faster solving performance than state-of-the-art MWCP solvers on standard benchmarks.

2 Preliminaries

Given an undirected simple graph G = (V,E,w), where V = {v1, v2, . . . , vn} is the vertex set, E is the edge set, and w : V → R≥0 assigns a non-negative weight to each vertex. The density of G is defined as 2|E|/(|V |(|V | - 1)). For each vertex vi ∈ V , we define w(vi) as the weight of it, and we also use vw(vi) i to represent vertex vi together with its weight w(vi). The neighbor set of vi is denoted as N(vi). For any clique C ⊆ V , its total weight is defined as w(C) = ∑vi∈C w(vi).

A weight independent set I ⊆ V is a set of pairwise non-adjacent vertices. The weight of I is defined as the maximum weight in I, i.e. w∗ (I) = maxvi∈I(w(vi)). Let I = {vw(v1) 1 , vw(v2) 2 , . . . , vw(vr) r } be aweight independent set whose vertices are sorted in non-increasing order of weights, i.e., w(v1) ≥ · · · ≥ w(vk) > β ≥ w(vk+1) ≥ · · · ≥ w(vr). The split operation split(I, β) divides I into two subsets: I ′ = {vβ 1 , vβ 2 , · · · , vβ k , vw(vk+1) k+1 , · · · , vw(vr) r } and I ′′ = {vw(v1)-β 1 , vw(v2)-β 2 , · · · , vw(vk)-β k }.

2.1 Basic BnB Framework for MWCP

Algorithm 1 outlines a basic BnB framework for MWCP. Given a weight graph G = (V,E,w), a candidate set P, a vertex ordering O and a partial clique S, the algorithm maintains the best clique C ∗ found so far. At each search node, it invokes GetBranches to divide P into two subsets, A and B. The vertices in A induce a subgraph whose maximum weight clique is bounded by w(C ∗ ) - w(S), and can therefore be pruned safely. The remaining vertices form the branching set B = P \ A = {b1, . . . , b|B|}. If B is empty, the current search branch is pruned, because the clique C can not grow to a clique of weight greater than w(C ∗ ). Otherwise, the algorithm branches on each vertex in B, from b|B| to b1, to search for a clique containing bi in the induced subgraph by N(bi) ∩ ({bi+1, · · · , b|B|} ∪ A). Whenever a clique with larger weight is found, C ∗ is updated accordingly.

The pruning effectiveness of the BnB framework largely depends on how GetBranches divides the candidate set. A good partition moves as many vertices as possible into A without violating the upper-bound condition, leaving fewer vertices in B to branch on. TSM-MWC [Jiang et al., 2018] follows this idea by adapting a two-stage MaxSAT reasoning inside GetBranches, which leads to tighter upper bounds and a smaller search tree.

2.2 MaxSAT Reasoning for MWCP

Before MaxSAT reasoning, TSM-MWC divides the candidate set P into two subsets by partitioning weight independent sets. Vertices covered by a set of independent sets Π = {I1, . . . , Ik} are grouped into A, such that ∑Ii∈Π w∗ (Ii) ≤ w(C ∗ ) - w(S), and all other vertices form B. A vertex may appear in multiple independent sets in Π, and its weight is distributed among these sets while keeping the total weight unchanged, i.e., w(v) = ∑Ii∈Π, v∈Ii wi(v), where wi(v) denotes the portion of v's weight assigned to Ii.

A conflict is a set of independent sets, fromwhich no clique can choose one vertex from each set. MaxSAT reasoning detects such conflicts through unit propagation (UP) to tighten the upper bound. During UP, the algorithm keeps track of the independent sets that contain only one vertex and removes all non-neighbors of this vertex from the other sets. If an independent set Ie becomes empty, a conflict is detected, consisting of Ie and the independent sets that caused all its vertices to be removed, and the upper bound is decreased. Vertices in B are tentatively added to A in the reverse order, and conflicts in the expanded set are analyzed. If the resulting upper bound is no greater than w(C ∗ ) - w(S), the vertex can be safely pruned.

More concretely, let Π denote the current independent sets. When a vertex from B is tentatively added to A, the resulting upper bound may violate the constraint, i.e. ub > w(C ∗ ) - w(S). In that case, MaxSAT reasoning searches for a conflict F = {I1, I2, . . . , Ik} ⊆ Π. Once such a conflict is found, it computes a shared weight β = min(w∗ (I1),w∗ (I2), . . . ,w∗ (Ik)). Each independent set Ii ∈ F is then split into two parts, I ′ i and I ′′ i , using split(Ii, β). The sets I ′ i all have weight β and together form a simplified conflict. These conflict sets are simply removed from further reasoning. The remaining parts, Π2 = {I ′′ i |w∗ (I ′′ i ) > 0}, are kept for subsequent reasoning. As a result, Π is updated to (Π \ F ) ∪ Π2, and the upper bound of A decreases from ub to ub - β.

3 ULE-MWC: An Efficient BnB Algorithm With an Unlocking-Enhanced Mechanism

In this section, we analyze the limitations of existing MaxSAT reasoning for MWCP. To overcome these limitations, we introduce two complementary strategies, the UnLocking Mechanism (ULM) and the Benefit-Enhanced Strategy (BES). By incorporating both strategies into the MaxSAT reasoning, we develop the enhanced BnB solver ULE-MWC.

3.1 Limitations of ExistingMaxSAT Reasoning

Although MaxSAT reasoning is effective for tightening upper bounds in MWCP, its current design has clear limitations.

Limitation 1: Irreversible shrinkage of the reasoning pool. InMaxSAT reasoning, once a conflict is detected, the independent sets involved are split, and the conflicting parts are removed from the subsequent reasoning process.

Example 1. Assume four independent sets I1, I2, I3, and I4, with weights w∗ (I1) = 1 and w∗ (I2) = w∗ (I3) = w∗ (I4) = 10. A conflict F = {I1, I2, I3} is detected, with a minimum weight of 1. After splitting and removing the conflicting parts {I1, I ′2 , I ′3 }, three independent sets left: I ′′ 2 and I ′′ 3 with weight 9, and I4 with weight 10.

In the early stages, this approach is often very efficient to reduce the upper bound, as the number of independent sets is relatively large. However, as the reasoning process continues, more conflicting independent sets are removed, and the pool of available independent sets gradually shrinks, making it harder to find new conflicts.

Figure 1 provides evidence of this limitation, obtained from TSM-MWC when solving benchmark instances. As more conflicts are detected, the number of independent sets steadily decreases, which directly limits further reasoning.

Limitation 2: Conflict detection without benefit awareness. Another limitation lies in conflict detection. Since independent sets are processed in a fixed order, conflict identification is highly order-dependent. Moreover, the reduction of the upper bound is governed by the smallest weight among the independent sets in the conflict. As a result, many conflicts involve low-weight independent sets, leading to small bound reductions while still costing the same reasoning effort as more useful conflicts. As a result, much time is spent on conflicts with little pruning effect.

Taken together, these limitations show that existing MaxSAT reasoning neither reuses conflicting independent sets nor focuses reasoning effort on the most effective conflicts. This motivates our two strategies: an UnLocking Mechanism to reuse conflict cores, and a Benefit-Enhanced Strategy to prioritize conflicts with higher pruning potential.

Algorithm 2: AddCore(F, Π, C, L)

Input: A conflict F, the set of independent sets Π, conflict cores C, locked independent sets L. Output: The updated Π, C and L and the reduced weight β. 1 β =minIi∈F w∗ (Ii); 2 Π′ ← ∅, c ← ∅; 3 c.w ← β, c.uw ← 0, c.active = true; 4 for Ii ∈ F do 5 (I ′ i , I ′′ i ) ← split(Ii, β); 6 Π′ ←Π′ ∪ {I ′′ i }; 7 L←L∪ {I ′ i }, I ′ i .unlock = false; 8 I ′ i .c = c, c ← c ∪ {I ′ i }; 9 if Ii ∈ L and (c′ = Ii.c, c′ .active = true) then 10 c′ .active = false, c.w ← c.w + c′ .w; 11 for Ij ∈ c′ do 12 c ← c ∪ {Ij}, Ij .c = c; 13 Π← (Π \ F) ∪Π′ , C ← C ∪ {c}; 14 return (Π, C, L, β);

3.2 Lookahead Through UnlockingMechanism

To enable the reuse of independent sets involved in conflicts, we introduce conflict cores to maintain the conflicts.

Definition 1 (Conflict Core). A conflict core c is a set of independent sets with a non-negative penalty value c.w. Let wt(c) = ∑I∈c w∗ (I) denote the total weights of the independent sets in c, and V (c) be the set of vertices with corresponding weights contained in these independent sets. The core satisfies: (core invariant) For any clique C ⊆ V (c), w(C) ≤ wt(c) - c.w.

During MaxSAT reasoning, independent sets may become empty due to propagation. Let c.uw denote the total weight of independent sets in c that have become empty. When c.uw ≥ c.w, the penalty enforced by the core is fully paid, and the Core Invariant is satisfied independently of the remaining independent sets. Hence, all remaining locked independent sets in c can be safely unlocked and reactivated without affecting the correctness of the upper bound.

Algorithm 2 describes how a conflict core is constructed from a detected conflict F. It first computes the minimum shared weight β among the independent sets in F (line 1) and initializes a new conflict core (lines 2-3). Each independent set in F is then split by β (line 5). The part with weight β is added to the new conflict core and locked to prevent immediate reuse (lines 7-8), while the remaining parts with positive weight are kept for reasoning (line 6). If the locked part originates from an existing active conflict core, that core is deactivated and merged into the new one, preserving previously derived conflict information (lines 9-12). Finally, the algorithm updates the pool of independent sets and the set of conflict cores (line 13).

Algorithm 3 extends basic MaxSAT reasoning by introducing conflict cores, so that independent sets involved in conflicts are not permanently removed but can be reused in subsequent reasoning. The algorithm incrementally tightens δ,

Algorithm 3: ULM-MaxSAT(Π, C, L, t, ub, δ)

which denotes the increase in the upper bound caused by tentatively adding the current branching vertex into A. Here, ub is the upper bound of the weight clique induced by the original A, and t = w(C ∗ ) -w(S) is the pruning threshold. The branch can be pruned once ub + δ ≤ t.

The procedure repeatedly performs propagation as long as there exists a unit independent set or an independent set in an unlocked conflict core (line 1). When a unit set {v} is found, all vertices non-adjacent to v are removed from all other independent sets (line 2). If this operation makes an independent set or an unlocked set empty, a conflict is detected (line 3). The independent sets responsible for this conflict are then collected (line 4), and a new conflict core is constructed by AddCore, which decreases δ by the extracted shared weight (lines 6-7). After each detected conflict, all previously removed vertices and all active conflict cores are restored (line 5). If ub + δ ≤ t, the reasoning stops (line 8).

For an empty locked independent set whose conflict core is still locked, its weight is accumulated into the corresponding core (lines 9-10). Once the accumulated weight reaches the penalty of the core, the Core Invariant is satisfied, and all remaining locked independent sets in the core are unlocked and reactivated for further reasoning (lines 11-13). The algorithm terminates when no further propagation is possible and returns the final value of δ (line 14).

Proposition 1 establishes the soundness of Algorithm 2.

Proposition 1. Every conflict core generated by Algorithm 2 satisfies the Core Invariant in Definition 1.

Proof. Let F = {I1, · · · , Ik} be the detected conflict, β = minIi∈F w∗ (Ii). By definition of conflict, no clique contained in ⋃Ii∈F Ii can simultaneously select vertices from all sets in F. Hence, any clique C ⊆ V (c) must lose at least β total weight relative to ∑ki=1 w∗ (Ii).

.

Case 1: The conflict core does not involve any independent set from existing cores. Algorithm 2 constructs a new conflict core c by locking weight β from each Ii ∈ F, and sets c.w = β. For any clique C ⊆ V (c), since no other conflict is involved, the above argument applies, w(C) ≤ ∑ki=1 w∗ (Ii) - β = wt(c) - c.w.

Case 2: The conflict involves independent sets from existing active conflict cores C ′ = {c1, . . . , cr}. By induction, we assume that each cj ∈ C ′ satisfies that for any clique C ⊆ V (cj), w(C) ≤ wt(cj) - cj.w. Algorithm 2 merges these cores and the newly locked independent sets into a new core c, with c.w = β + ∑rj=1 cj .w.

We divide the sets in c into two groups. The first group consists of independent sets that do not belong to any core in C ′ . If any independent set in this group does not contribute a vertex to a clique, the Core Invariant holds immediately.

Otherwise, all independent sets in the first group contribute vertices to the clique. The cores in C ′ are subsumed into c because, during propagation, the accumulated weight of empty independent sets cj.uw ≥ cj.w, thereby satisfying the penalty of that core and allowing its remaining independent sets to re-enter conflict reasoning. Under this condition, the newly detected conflict necessarily forces at least one additional independent set, which is possibly from an unlocked core in C ′ , to become empty, contributing a weight of at least β. This empty independent set is not used to satisfy the unlocking condition of its original core, but instead accounts for the penalty of the newly constructed conflict core.

Hence, the Core Invariant holds for the newly constructed core. By induction, it holds for all conflict cores maintained by Algorithm 2.

To illustrate how conflict cores participate in MaxSAT reasoning, we present an example abstracted from a real benchmark instance. The overall reasoning process is shown in Figure 2, and the analysis of the resulting penalty value of the core is illustrated in Figure 3.

Example 2. Consider one independent set I1 = {v20 1 } and two existing conflict cores:

where c1.w = 1, c2.w = 5, and all locked independent sets in c1 have weight 1 and those in c2 have weight 5.

𝑤 = min 20,5,1 +𝑤 𝑐! +𝑤(𝑐%) = 7

Figure 3: Analyze weight of new core

Algorithm 4: PrepareBES(Π, wc)

Input: Independent sets Π, integer wc Output: Filtered independent sets Π′ . 1 wth ← min(wg, wc/cg), Π′ ← ∅; 2 for Ii ∈ Π do 3 if w∗ (Ii) ≥ wth then Π′ ← Π′ ∪ {Ii} ; 4 return Π′ ;

Since I1 is a unit independent set, the algorithm removes all non-neighbors of v1 from all independent sets, namely v2, v3, v4, v7, and v8. This makes LI1 empty. As LI1 is locked and c1.uw = w∗ (LI1) = c1.w, the Core Invariant of c1 is satisfied and c1 is unlocked, enabling LI2 and LI3 to participate in further reasoning. Similarly, LI4 becomes empty, unlocking c2 and allowing LI5 and LI6 to join the propagation. Next, LI2 = {v5} becomes a unit unlocked independent set. Removing its non-neighbor v11 makes LI6 empty. Since the core of LI6 is unlocked, a new conflict is detected.

During conflict analysis, the algorithm starts from the empty set LI6 and traces back all independent sets responsible for vertex removals until closure. Figure 3 provides an explanation of the resulting penalty of the conflict core. If I1 contributes no vertex, the clique weight is reduced by 20. Otherwise, cores c1 and c2 are involved: since LI1 and LI4 cannot contribute vertices, either LI2 also fails to contribute (yielding a reduction of 5), or LI6 fails (yielding a reduction of 1). Hence, the minimum guaranteed reduction is selected.

After invoking AddCore, I1 is split into I ′1 = {v1 1 } and I ′′ 1 = {v19 1 }, where I ′′ 1 can participate in the reasoning process. Cores c1 and c2 are deactivated and merged into the new conflict core c3 = {LI1,LI2,LI3,LI4,LI5,LI6, I ′1 }, with total weight c3.w = c1.w + c2.w + min(20, 5, 1) = 7. The weights of LI1,LI2,LI3, and I ′1 are 1, while those of LI4, LI5, and LI6 are 5.

3.3 Benefit-Enhanced Strategy

Example 1 shows that a single reasoning round reduces δ by only 1. When the gap ub+δ-t is large, this reduction is insufficient. Since the reduction in each round largely depends on the independent sets involved, it is crucial to focus on those that can yield a meaningful decrease in the bound.

Motivated by this observation, we propose a Benefit-

Algorithm 5: ULE-MaxSAT(G, O, B, Π, t, ub)

Input: G = (V, E, w), vertex order O, branching set B, independent sets Π on A = P \ B, integer t, and upper bound ub = w(G[A]). Output: The reduced branching set B. 1 B = {b1, b2, · · · , b|B|}, b1 < b2 < · · · < b|B| w.r.t. O; 2 L ← ∅ be the Ls, C ← ∅ be the conflict cores; 3 for i = |B| down to 1 do 4 Π′ ←Π, L′ ←L, C ′ ← C, δ ←w(bi); 5 Π←PrepareBES(Π, ub + δ - t); 6 Let I1, · · · , Ik with Ij ∩N(bi) = ∅ (j = 1, . . . , k); 7 for j = 1 to k do 8 Ij ← Ij ∪ {bw∗ (Ij) i }, δ ← δ -w∗ (Ij); 9 Let U1, · · · ,Ur with |Uj ∩N(bi)| = 1 (j = 1, . . . , r); 10 for j = 1 to r do 11 Let N(bi) ∩ Uj = {u}; 12 if ∃Iq ∈ Π s.t. N(u) ∩ N(bi) ∩ Iq = ∅ then 13 F = {Iq , Uj , {bδi }}; 14 (Π, C, L, β) = AddCore(F, Π, C, L); 15 δ ← δ - β; 16 if ub + δ ≤ t then break; 17 if ub + δ > t then 18 Π ← Π ∪ {{bδi }}; 19 δ ← ULM-MaxSAT(Π, C, L, t, ub, δ); 20 Restore I removed by BES; 21 if ub + δ ≤ t then 22 B ← B \ {bi}, ub ← ub + δ; 23 else 24 Π ← Π′ , L ← L′ , C ← C ′ ;

25 return B;

Enhanced Strategy that adaptively preselects independent sets according to the current pruning demand and global graph characteristics. Algorithm 4 first computes a weight threshold wth = min(wg, wc/cg), where wc = δ+ub-t is the remaining bound gap. Independent sets with weight below wth are filtered out (line 1). The remaining sets with w∗ (Ii) ≥ wth are collected into Π′ (lines 2-3) and passed to subsequent MaxSAT reasoning (line 4).

The parameter cg is chosen based on the graph size n: cg = 2 for n ≤ 5 × 105 , cg = 3 for n ≤ 106 , cg = 5 for n ≤ 1.5 × 106 , and cg = 8 otherwise. The global threshold wg is set to wavg/cg, where wavg is the average vertex weight. For small graphs, branching is relatively cheap and aggressive pruning is unnecessary. For large graphs, branching becomes much more costly, and stronger pruning is therefore needed.

3.4 EnhancedMaxSAT Reasoning

Algorithm 5 presents the ULE-MaxSAT framework, which integrates ULM and BES to strengthen MaxSAT reasoning. It first initializes the branching set B, the locked independent sets L, and the conflict cores C (lines 1-2). ULE-MaxSAT

Algorithm 6: GetBranches(G, t, O)

Input: G = (V, E, w), an integer t and an ordering O Output: The branching set B 1 (B,Π, ub) ←get the initial independent sets; 2 if B is not empty then 3 B ←ULE-MAXSAT(G,O,B,Π, t, ub); 4 return B;

Algorithm 7: ULE-MWC(G)

Input: G = (V, E, w) Output: Maximum weight clique C ∗ 1 (C0,O0,G′ ) ← Initialize(G, 0); 2 C ∗ ← C0, V ′ ← vertices in G′ ordered w.r.t. O0; 3 for i = |V ′ | downto 1 do 4 S ← {vi}, P ←N(vi) ∩ {vi+1, · · · , v|V ′ |}; 5 if w(P ) + w(S) > w(C ∗ ) then 6 (C ′0 , O′0 , G′′ ) ← Initialize(G′ [P ], w(C ∗ ) - w(S)); 7 if w(S) + w(C ′0 ) > w(C ∗ ) then 8 C ∗ ← S ∪ C0; 9 V ′′ ← vertices in G′′ ordered w.r.t. O′0 C1 ← BnB(G′′ , V ′′ , O′0 , S, C ∗ ); 10 if w(C1) > w(C ∗ ) then C ∗ ← C1; 11 return C ∗ ;

follows TSM-MWC [Jiang et al., 2018] by prioritizing the detection of conflict cores involving two or three independent sets (lines 3-16), but instead of removing the conflicting parts, it maintains them in conflict cores for later reuse (line 14). After that, ULM-MaxSAT is applied to the remaining independent sets together with the stored cores, enabling further pruning of B (lines 17-19). The final branching set is then updated (lines 21-22). If no pruning can be applied, all independent sets, conflict cores, and locked independent sets are restored to their previous states (lines 23-24).

Algorithm 6 shows the GetBranches procedure used in the BnB framework. It first obtains the initial branching set B through partitioning independent sets Π, and then refines B using ULE-MaxSAT.

3.5 The Framework of ULE-MWC

Algorithm 7 presents the overall ULE-MWC framework. It follows the main structure of TSM-MWC and modifies only the MaxSAT reasoning within the BnB procedure. The algorithm initializes an initial clique, a vertex ordering, and a reduced graph, then explores candidate cliques using BnB, and finally returns the maximum weight clique found. Details of the preprocessing steps are omitted and can be found in WLMC and TSM-MWC.

4 Experimental Results

In this section, we compare ULE-MWC with two stateof-the-art BnB solvers, TSM-MWC and WLMC, on three benchmark datasets and present ablation studies to evaluate the effectiveness of ULM and BES.

4.1 Experiment Preliminaries

Benchmark Datasets. We evaluate ULE-MWC on three benchmark types:

• DIMACS2 graphs: 80 graphs up to 4000 vertices, densities 0.03-0.99 1 .
• Real-world massive graphs: 77 graphs from the Network Data Repository [Rossi and Ahmed, 2015], including those used for WLMC and TSM-MWC 2 .
• Graphs from MWC practical applications: Four application groups: 15 from error-correcting codes (ECC), 100 from kidney exchange schemes (KES), 129 from the Research Excellence Framework (REF), and 499 from the winner determination problem (WDP). The complete ECC, KES, and REF, along with a subset of the WDP instances, were collected by [McCreesh et al., 2017] 3 .

Solvers. We evaluate our ULE-MWC 4 against two stateof-the-art BnB solvers TSM-MWC [Jiang et al., 2018] and WLMC [Jiang et al., 2017] 5 .

To evaluate the effectiveness of our ULM and BES, we generate two variants of ULE-MWC, called ULE-MWCnoBES (removing BES) and ULE-MWCnoULM (removing ULM).

Experimental Setup. ULE-MWC is implemented in C and tested on an AMD EPYC 7H12 server running Ubuntu 18.04. All experiments use a time limit of 10,000 seconds. We report the solution time (in seconds) and the number of explored branches (×105 ). A dash ("-") means that the solver fails to finish within the time limit. Best results are highlighted in bold.

4.2 Performance Comparison

TSM-MWC has proven to be very effective in practice, leaving little room for improvement. As a result, achieving better performance than it is a challenging task.

We first evaluate ULE-MWC on both DIMACS2 instances and real-world massive graphs (MASSIVE). As shown in Table 1, ULE-MWC consistently demonstrates superior or competitive performance compared with TSM-MWC and WLMC. On DIMACS2, ULE-MWC often achieves the smallest search tree or the fastest runtime, particularly on larger instances such as the brock800 and gen400 series, where it reduces solution time by several hundred seconds compared with TSM-MWC and significantly outperforms WLMC. Notably, on the Keller5 instance, neither TSMMWC nor WLMC can obtain an exact solution within the time limit, whereas our ULE-MWC does, which highlights the strong pruning capability and high efficiency of our approach. ULE-MWC shows competitive or better results on massive graphs. It achieves the fastest runtime on most brain-network instances, highlighting its efficiency in handling large-scale graphs.

1 available at http://archive.dimacs.rutgers.edu/Challenges/

2 available at http://networkrepository.com

3 available at https://doi.org/10.5281/zenodo.816293

4 The source code of ULE-MWC is available at https://github.com/LlzmMing/ULE-MWC.git

5 The source codes of both TSM-MWC and WLMC are available at https://home.mis.u-picardie.fr/˜cli/EnglishPage.html

We further test ULE-MWC on practical MWCP applications, including ECC, KES, REF, and WDP instances, and summarize the results in Table 2. ULE-MWC solves all 15 ECC and 499 WDP instances, and 84 KES and 106 REF

instances, matching or exceeding the number of instances solved by TSM-MWC and WLMC. In terms of runtime, ULE-MWC consistently outperforms the baselines, achieving the lowest average solution time across all four datasets.

For the KES instances, we further compute the average runtime over the eight instances requiring more than 5 seconds: TSM-MWC needs 1710s on average, while ULEMWC only requires 1580s, indicating better efficiency.

4.3 Ablation Studies

To evaluate the effectiveness of our proposed strategies, we conduct ablation studies on ULE-MWC by removing the BES (ULE-MWCnoBES) and ULM (ULE-MWCnoULM) components. As shown in Table 3, removing BES generally increases runtime across most datasets, especially on DIMACS and MASSIVE instances, indicating that the BES strategy effectively accelerates the search process. Similarly, ULEMWCnoULM exhibits larger search trees on DIMACS and MASSIVE datasets compared with the full ULE-MWC, confirming that the ULM strategy contributes to efficient pruning of the search space.

5 Conclusion

In this paper, we analyze the limitations of existing MaxSATbased bounding for the Maximum Weight Clique Problem. Independent sets in conflicts are discarded after one use, and conflicts are processed in a fixed order regardless of their pruning effectiveness, which restricts the reuse of conflict information and weakens bound tightening. To address these issues, we introduce two complementary techniques. The UnLocking Mechanism preserves conflict cores to enable the reuse of informative independent sets, while the BenefitEnhanced Strategy guides MaxSAT reasoning toward conflicts with higher pruning potential. By integrating them into a unified BnB solver, ULE-MWC, we obtain consistently tighter upper bounds and superior performance over state-ofthe-art MWCP solvers on standard benchmarks.

Acknowledgements

This work is partially supported by the French National Research Agency (ANR) under the Chair MASSAL'IA (ANR19-CHIA-0013-01), co-funded by the French electricity distribution network operator Enedis.