Introduction
Let G G G be a simple undirected graph and let k k k be a positive integer. A set of vertices is k k k -independent if the distance between any two distinct vertices in the set exceeds k k k . Its maximum possible cardinality is the k k k -independence number, denoted by α k ( G ) \alpha_k(G) α k ( G ) . This generalizes the usual independence number and describes separation requirements in coding theory and location problems. In particular, distance-independent sets in Hamming and sum-rank-metric graphs correspond to codes with a prescribed minimum distance [4 ] .
Finding a maximum k k k -independent set is NP-hard for every fixed positive k k k [18 , 19 , 5 , 12 ] . The problem can be expressed as an independent set problem in the graph power G k G^k G k , which joins vertices whose distance in G G G is at most k k k , or as a clique problem in its complement [2 , 3 ] . This permits the use of established maximum clique algorithms; see the surveys [8 , 31 ] . Integer programming provides another approach, with the advantage that additional inequalities and side constraints can be incorporated directly. Martins [22 ] develops the size-indexed formulation used as our computational reference. Sequential fixed-size searches also appear in methods for related graph optimization problems [29 ] .
Spectral graph theory provides a complementary source of information. Bounds for the k k k -independence number derived from the spectrum of the original graph have been developed in [1 , 2 , 3 , 4 , 7 , 6 ] . Such bounds may rule out larger solutions before an expensive search is required. They can also be applied locally to restrict how many vertices a solution may select from a given subset. This second use connects spectral bounds with the classical rank inequalities and lifting methods used in stable set optimization [9 , 23 , 26 , 25 ] .
In this paper, we develop a branch-and-cut framework that combines these ideas for distance independence. We solve a sequence of fixed-size clique problems on reduced auxiliary graphs. Compared with Martins’ formulation, each subproblem avoids maintaining separate copies of the vertex variables for all candidate clique sizes. We establish the correctness of the formulation and derive stronger combinatorial and spectral inequalities tailored to the chosen solution size. We also show how information about a subset of vertices can restrict the choices made elsewhere in the graph. The contribution lies in this formulation and its inequalities, together with their integration into the sequential method.
The spectral inequalities use established independence bounds on the power graph and on complements of subgraphs of the current working graph. This differs from optimizing polynomial bounds directly from the spectrum of the original graph. We show how to use the local bounds after vertex and edge reductions and how to strengthen the resulting inequalities. These results strengthen the optimization model while using established eigenvalue bounds.
We evaluate a reference implementation on several Sagemath named graphs and coding-theoretic graphs such as sum-rank-metric graphs for four distance thresholds. The configuration combining both cut families reports optimality in 470 of 544 cases, compared with 416 for the tested discretized formulation. We examine the contribution of the cut families and the time spent on successive target sizes, and include additional comparisons on DIMACS graphs.
Reduction to the maximum clique problem
Notation All graphs are finite, simple, and undirected. We assume ∣ V ∣ ≥ 1 |V| \ge1 ∣ V ∣ ≥ 1 unless stated otherwise; for the graph with no vertices, α k ( G ) = 0 \alpha_k(G) = 0 α k ( G ) = 0 . The distance dist G ( i , j ) \operatorname{dist}_G(i,j) dist G ( i , j ) is the number of edges on a shortest path from i i i to j j j , and is infinite when the vertices lie in different connected components. When such a path exists, S P G ( i , j ) SP_G(i,j) S P G ( i , j ) denotes one shortest path, viewed as an ordered vertex sequence. For a graph H = ( U , F ) H = (U,F) H = ( U , F ) , write H [ W ] H[W] H [ W ] for the subgraph induced by W ⊆ U W \subseteq U W ⊆ U , H ‾ \overline{H} H for its complement, N H ( i ) N_H(i) N H ( i ) for the open neighborhood of i i i , and d H ( i ) = ∣ N H ( i ) ∣ d_H(i) = |N_H(i)| d H ( i ) = ∣ N H ( i ) ∣ for its degree. We write y ( W ) = ∑ i ∈ W y i y(W) = \sum_{i \in W} y_i y ( W ) = ∑ i ∈ W y i and use ω ( H ) \omega(H) ω ( H ) and α 1 ( H ) \alpha_1(H) α 1 ( H ) for the clique and independence numbers. The notation G ‾ = G k \overline{G} = G^k G = G k is reserved for the original auxiliary graph; H H H denotes a current working graph and H q = ( V q , E q ) H_q = (V_q,E_q) H q = ( V q , E q ) the graph after reductions for target size q q q .
For a graph H H H , let ω ( H ) \omega(H) ω ( H ) denote its clique number, with ω ( ∅ ) = 0 \omega(\varnothing)=0 ω ( ∅ ) = 0 . Given an instance G = ( V , E ) G=(V,E) G = ( V , E ) of k k k -MIS, define the auxiliary graph
G ‾ = ( V , E ‾ ) , E ‾ = { { i , j } ∈ ( V 2 ) : dist G ( i , j ) > k } . \overline{G}=(V,\overline{E}), \qquad\overline{E}=\left\{\{i,j\}\in\binom{V}{2}:\operatorname{dist}_{G}(i,j)>k\right\}. G = ( V , E ) , E = { { i , j } ∈ ( 2 V ) : dist G ( i , j ) > k } .
Thus G ‾ = G k \overline{G}=G^{k} G = G k , and the definitions give
α k ( G ) = α 1 ( G k ) = ω ( G ‾ ) . (1) \alpha_{k}(G)=\alpha_{1}(G^{k})=\omega(\overline{G}). \tag*{(1)} α k ( G ) = α 1 ( G k ) = ω ( G ) . (1)
Indeed, a set of vertices has pairwise distance greater than k k k in G G G if and only if all its pairs are edges of G ‾ \overline{G} G [3 , 2 ] . The auxiliary graph can be constructed in polynomial time by computing shortest-path distances [20 ] ; vertices in different connected components of G G G are adjacent in G ‾ \overline{G} G . The empty input graph has α k ( G ) = 0 \alpha_{k}(G)=0 α k ( G ) = 0 and is handled directly. For the remainder of this section, assume V ≠ ∅ V\ne\varnothing V = ∅ .
A compact formulation for a fixed clique size
The discretized formulation of Martins [22 ] represents the possible clique sizes explicitly. Let Q ⊆ { 1 , … , ∣ V ∣ } Q\subseteq\{1,\ldots,|V|\} Q ⊆ { 1 , … , ∣ V ∣ } contain ω ( G ‾ ) \omega(\overline{G}) ω ( G ) . The binary variable w q w_q w q selects size q q q , and x i q x_{iq} x i q indicates whether vertex i i i belongs to the clique selected at that size. The formulation is
max ∑ i ∈ V ∑ q ∈ Q x i q (2) \max\sum_{i\in V}\sum_{q\in Q}x_{iq} \tag*{(2)} max i ∈ V ∑ q ∈ Q ∑ x i q (2)
s.t. ∑ q ∈ Q w q = 1 , (3) \text{s.t.}\qquad\sum_{q\in Q}w_q=1, \tag*{(3)} s.t. q ∈ Q ∑ w q = 1 , (3)
∑ j ∈ N G ‾ ( i ) x j q ≥ ( q − 1 ) x i q ∀ i ∈ V , q ∈ Q , (4) \sum_{j\in N_{\overline{G}}(i)}x_{jq}\ge(q-1)x_{iq}\qquad\forall i\in V,\ q\in Q, \tag*{(4)} j ∈ N G ( i ) ∑ x j q ≥ ( q − 1 ) x i q ∀ i ∈ V , q ∈ Q , (4)
∑ i ∈ V x i q = q w q ∀ q ∈ Q , (5) \sum_{i\in V}x_{iq}=qw_q\qquad\forall q\in Q, \tag*{(5)} i ∈ V ∑ x i q = q w q ∀ q ∈ Q , (5)
w q ∈ { 0 , 1 } ∀ q ∈ Q , (6) w_q\in\{0,1\}\qquad\forall q\in Q, \tag*{(6)} w q ∈ { 0 , 1 } ∀ q ∈ Q , (6)
x i q ∈ { 0 , 1 } ∀ i ∈ V , q ∈ Q (7) x_{iq}\in\{0,1\}\qquad\forall i\in V,\ q\in Q \tag*{(7)} x i q ∈ { 0 , 1 } ∀ i ∈ V , q ∈ Q (7)
Exactly one size is active. At that size, every selected vertex has the other q − 1 q-1 q − 1 selected vertices as neighbors, so the selected set is a clique. The assumption on Q Q Q therefore makes the optimal objective value equal to ω ( G ‾ ) \omega(\overline{G}) ω ( G ) . The number of variables grows with ∣ Q ∣ |Q| ∣ Q ∣ , which motivates solving one size at a time.
Let H = ( U , F ) H=(U,F) H = ( U , F ) be the working auxiliary graph: initially H = G ‾ H=\overline{G} H = G , and after preprocessing it is the reduced graph defined in § 2.3 . We write N H ( i ) N_H(i) N H ( i ) and d H ( i ) d_H(i) d H ( i ) for its neighborhoods and degrees. For a fixed integer q ≥ 1 q\ge1 q ≥ 1 , consider
max ∑ i ∈ U y i (8) \max\sum_{i\in U}y_i \tag*{(8)} max i ∈ U ∑ y i (8)
s.t. ∑ j ∈ N H ( i ) y j ≥ ( q − 1 ) y i ∀ i ∈ U , (9) \text{s.t.}\qquad\sum_{j\in N_H(i)}y_j\ge(q-1)y_i\qquad\forall i\in U, \tag*{(9)} s.t. j ∈ N H ( i ) ∑ y j ≥ ( q − 1 ) y i ∀ i ∈ U , (9)
∑ i ∈ U y i = q z , (10) \sum_{i\in U} y_i = qz, \tag*{(10)} i ∈ U ∑ y i = q z , (10)
y i ∈ { 0 , 1 } ∀ i ∈ U , (11) y_i \in\{0,1\}\qquad\forall i\in U, \tag*{(11)} y i ∈ { 0 , 1 } ∀ i ∈ U , (11)
z ∈ [ 0 , 1 ] . (12) z \in[0,1]. \tag*{(12)} z ∈ [ 0 , 1 ] . (12)
Here y y y selects the vertices, while z z z permits either a q q q -clique or the empty solution. The variable z z z is continuous.
Proposition 2.1 (Exactness of the fixed-size formulation). For every finite simple graph H H H and every integer q ≥ 1 q \ge1 q ≥ 1 , the feasible solutions of (8) –(12) are precisely ( y , z ) = ( 0 , 0 ) (y,z)=(0,0) ( y , z ) = ( 0 , 0 ) and ( y , z ) = ( 1 C , 1 ) (y,z)=(\mathbf{1}_C,1) ( y , z ) = ( 1 C , 1 ) , where C C C is a clique of size q q q in H H H . Consequently, its optimal objective value is q q q if such a clique exists and 0 0 0 otherwise.
Proof. Let ( y , z ) (y,z) ( y , z ) be feasible and set C = { i ∈ U : y i = 1 } C=\{i\in U:y_i=1\} C = { i ∈ U : y i = 1 } . If C = ∅ C=\varnothing C = ∅ , then (10) and q ≥ 1 q\ge1 q ≥ 1 give z = 0 z=0 z = 0 . Otherwise, choose i ∈ C i\in C i ∈ C . Constraint (9) gives at least q − 1 q-1 q − 1 selected neighbors of i i i , and hence ∣ C ∣ ≥ q |C|\ge q ∣ C ∣ ≥ q . On the other hand, (10) and z ≤ 1 z\le1 z ≤ 1 give ∣ C ∣ ≤ q |C|\le q ∣ C ∣ ≤ q . Thus ∣ C ∣ = q |C|=q ∣ C ∣ = q and z = 1 z=1 z = 1 . Applying (9) to each i ∈ C i\in C i ∈ C shows that i i i is adjacent to every vertex of C ∖ { i } C\setminus\{i\} C ∖ { i } , so C C C is a clique. Conversely, the empty solution and the incidence vector of any q q q -clique satisfy every constraint. The argument also covers q = 1 q=1 q = 1 and U = ∅ U=\varnothing U = ∅ .
The formulation has ∣ U ∣ |U| ∣ U ∣ binary variables, one continuous variable, and ∣ U ∣ + 1 |U|+1 ∣ U ∣ + 1 linear constraints apart from variable bounds, with O ( ∣ U ∣ + ∣ F ∣ ) O(|U|+|F|) O ( ∣ U ∣ + ∣ F ∣ ) nonzero coefficients. Eliminating z z z gives the equivalent formulation obtained by replacing (10) and (12) with ∑ i ∈ U y i ≤ q \sum_{i\in U} y_i\le q ∑ i ∈ U y i ≤ q . We retain z z z because it provides a useful strengthening of the cuts in § 3 . The LP relaxation also implies
0 ≤ y i ≤ z ( i ∈ U ) : (13) 0 \le y_i \le z \qquad(i\in U): \tag*{(13)} 0 ≤ y i ≤ z ( i ∈ U ) : (13)
indeed, (9) and (10) give ( q − 1 ) y i ≤ ∑ j ∈ N H ( i ) y j ≤ q z − y i (q-1)y_i\le\sum_{j\in N_H(i)}y_j\le qz-y_i ( q − 1 ) y i ≤ ∑ j ∈ N H ( i ) y j ≤ q z − y i .
Relation to the experimental implementation
The implementation used in § 6 declares z z z binary and retains the additional rows
∑ j ∈ N H ( i ) y j ≤ q − y i ( i ∈ U ) . (14) \sum_{j\in N_H(i)} y_j \le q-y_i \qquad(i\in U). \tag*{(14)} j ∈ N H ( i ) ∑ y j ≤ q − y i ( i ∈ U ) . (14)
Proposition 2.1 shows that the integrality restriction on z z z does not change the integer feasible solutions. Moreover, (14) is redundant even in the LP relaxation, since
∑ j ∈ N H ( i ) y j ≤ ∑ j ∈ U ∖ { i } y j = q z − y i ≤ q − y i . \sum_{j\in N_H(i)} y_j \le\sum_{j\in U\setminus\{i\}} y_j = qz-y_i \le q-y_i. j ∈ N H ( i ) ∑ y j ≤ j ∈ U ∖ { i } ∑ y j = q z − y i ≤ q − y i .
The compact formulation and the implementation therefore have the same integer feasible solutions and the same LP relaxation.
Algorithm 1 Graph reduction for a target clique size
1 Input: auxiliary graph $\bar{G} = (V, \bar{E})$ and integer $q \ge 2$
2 $H = (U, F) \gets \bar{G}$
3 while a vertex or edge of $H$ satisfies a deletion rule do
4 if there is a vertex $i \in U$ with $d_H(i) < q - 1$ then
5 delete $i$ and its incident edges from $H$
6 else
7 choose $\{i,j\} \in F$ with $\lvert N_H(i) \cap N_H(j)\rvert < q - 2$
8 delete $\{i,j\}$ from $H$
9 end if
10 end while
11 Output: $H_q = (V_q, E_q) \gets H$
Reduction of graph size
For q ≥ 2 q \ge2 q ≥ 2 , two deletion rules reduce the auxiliary graph before the fixed-size problem is solved: a vertex i i i may be deleted when d H ( i ) < q − 1 d_H(i) < q - 1 d H ( i ) < q − 1 , and an edge { i , j } \{i,j\} { i , j } may be deleted when ∣ N H ( i ) ∩ N H ( j ) ∣ < q − 2 \lvert N_H(i) \cap N_H(j)\rvert< q - 2 ∣ N H ( i ) ∩ N H ( j )∣ < q − 2 . Degrees and common neighborhoods are evaluated in the current graph, so a deletion may enable further deletions. Algorithm 1 applies the rules until neither is possible. Related degree and common-neighbor restrictions appear in Martins [22 ] ; core and truss reductions are standard preprocessing tools for maximum clique [10 , 30 ] . The case q = 1 q = 1 q = 1 needs no reduction: a nonempty graph contains a one-vertex clique.
Proposition 2.2 (Validity and uniqueness of the reduction). For q ≥ 2 q \ge2 q ≥ 2 , Algorithm 1 terminates and preserves every clique of G ˉ \bar{G} G ˉ of size at least q q q . Its output is independent of the order of valid deletions and is the unique largest subgraph of G ˉ \bar{G} G ˉ in which every vertex has degree at least q − 1 q - 1 q − 1 and the endpoints of every edge have at least q − 2 q - 2 q − 2 common neighbors.
Proof. Each iteration deletes a vertex or an edge, so the algorithm terminates after at most ∣ V ∣ + ∣ E ˉ ∣ \lvert V\rvert+\lvert\bar{E}\rvert ∣ V ∣ + ∣ E ˉ ∣ iterations. Let C C C be a clique of size at least q q q . As long as all its vertices and edges remain, each vertex of C C C has at least q − 1 q - 1 q − 1 neighbors in C C C , and each edge of C C C has at least q − 2 q - 2 q − 2 common neighbors in C C C . Neither rule can therefore remove the first vertex or edge of C C C .
For uniqueness, let J J J be any subgraph of G ˉ \bar{G} G ˉ satisfying both degree conditions in the statement. If J J J is contained in the current graph, neither rule can delete a vertex or edge belonging to J J J , because its degree or common-neighbor count in the current graph is at least the corresponding count in J J J . Induction shows that every such J J J is contained in the terminal graph. The terminal graph itself satisfies both conditions, so it is the unique largest one, regardless of deletion order.
The vertex rule alone produces the ( q − 1 ) (q - 1) ( q − 1 ) -core. With both rules, the result is the q q q -truss, allowing disconnected components and excluding isolated vertices: every edge lies in at least q − 2 q - 2 q − 2 triangles [10 ] . Indeed, an endpoint of an edge with q − 2 q - 2 q − 2 common neighbors has degree at least q − 1 q - 1 q − 1 . For q ′ ≥ q ≥ 2 q' \ge q \ge2 q ′ ≥ q ≥ 2 , Proposition 2.2 also gives H q ′ ⊆ H q H_{q'} \subseteq H_q H q ′ ⊆ H q , since the terminal graph for q ′ q' q ′ satisfies the conditions for q q q .
Figure 1 illustrates the effect of vertex deletion. The graph has clique number 3, while the displayed fractional solution has value 4 in the LP relaxation of (8) –(12) at q = 4 q = 4 q = 4 . It is LP-optimal because (10) gives ∑ i y i ≤ 4 \sum_i y_i \le4 ∑ i y i ≤ 4 . The vertices 4, 5, and 6 have degree 2 and are deleted first. The remaining triangle then has degree 2 at each vertex and is also deleted, certifying that no four-vertex clique exists.
Figure 1. The graph reduction example. Vertex labels give the vertex index and, in parentheses, its value in an optimal solution of the LP relaxation of (8) –(12) for q = 4 q = 4 q = 4 .
The distinction between the original and reduced auxiliary graphs matters for cut validity. Because edges as well as vertices are deleted, H q ‾ \overline{H_q} H q need not be an induced subgraph of G ‾ \overline{G} G ; in particular, H q ‾ \overline{H_q} H q need not equal G k [ V q ] G^k[V_q] G k [ V q ] . A cut valid for every clique of H q H_q H q is valid for the fixed-q q q problem by Proposition 2.2 , but need not be valid for every clique of the original auxiliary graph. For example, if two triangles are joined by a bridge u v uv uv , the reduction for q = 3 q = 3 q = 3 deletes the bridge and keeps both triangles. The inequality y u + y v ≤ 1 y_u + y_v \le1 y u + y v ≤ 1 is then valid for the reduced graph, although { u , v } \{u,v\} { u , v } is a clique of the original graph.
Combinatorial cuts
Throughout this section, H = ( U , F ) H = (U,F) H = ( U , F ) denotes the current auxiliary graph. For W ⊆ U W \subseteq U W ⊆ U , write y ( W ) = ∑ i ∈ W y i y(W) = \sum_{i \in W} y_i y ( W ) = ∑ i ∈ W y i . A clique intersects W W W in at most ω ( H [ W ] ) = α 1 ( H [ W ] ‾ ) \omega(H[W]) = \alpha_1(\overline{H[W]}) ω ( H [ W ]) = α 1 ( H [ W ] ) vertices. Thus any certified upper bound r ( W ) ≥ ω ( H [ W ] ) r(W) \ge\omega(H[W]) r ( W ) ≥ ω ( H [ W ]) gives a valid inequality
y ( W ) ≤ r ( W ) . (15) y(W) \le r(W). \tag*{(15)} y ( W ) ≤ r ( W ) . (15)
When the right-hand side is exact, this is a rank inequality for the stable set polytope of H ‾ \overline{H} H ; using an upper bound gives a valid relaxation of that inequality [9 , 26 , 25 ] . For H = G ‾ H = \overline{G} H = G , the complement is G k G^k G k ; after reduction, validity for the target problem follows from Proposition 2.2 . The families below differ in the combinatorial certificate for r ( W ) r(W) r ( W ) and in whether coefficients are lifted. § 4.2 replaces the combinatorial certificate with a spectral one.
Proposition 3.1 (Scaling a valid inequality by z z z ). Suppose that c ∈ R U c \in\mathbb{R}^{U} c ∈ R U and r ≥ 0 r \ge0 r ≥ 0 satisfy ∑ i ∈ C c i ≤ r \sum_{i \in C} c_i \le r ∑ i ∈ C c i ≤ r for every q q q -clique C C C of H H H . Then
∑ i ∈ U c i y i ≤ r z (16) \sum_{i \in U} c_i y_i \le rz \tag*{(16)} i ∈ U ∑ c i y i ≤ r z (16) is valid for (8) –(12) and dominates ∑ i c i y i ≤ r \sum_i c_i y_i \le r ∑ i c i y i ≤ r on 0 ≤ z ≤ 1 0 \le z \le1 0 ≤ z ≤ 1 . In particular, y ( W ) ≤ r ( W ) z y(W) \le r(W)z y ( W ) ≤ r ( W ) z is valid whenever r ( W ) ≥ ω ( H [ W ] ) r(W) \ge\omega(H[W]) r ( W ) ≥ ω ( H [ W ]) .
Proof. By Proposition 2.1 , a feasible solution is either ( 0 , 0 ) (0,0) ( 0 , 0 ) , for which (16) is an equality, or ( 1 C , 1 ) (\mathbf{1}_C,1) ( 1 C , 1 ) for a q q q -clique C C C , for which it is the assumed inequality. Since r ≥ 0 r \ge0 r ≥ 0 and z ≤ 1 z \le1 z ≤ 1 , its right-hand side is at most r r r . This also covers r = 0 r = 0 r = 0 and an empty working graph.
We present both the unscaled inequalities used in the computational study and the strengthened forms supplied by Proposition 3.1 . The reported experiments do not evaluate the z z z -scaled variants. For separation, let ( y ˉ , z ˉ ) (\bar{y}, \bar{z}) ( y ˉ , z ˉ ) be the current LP solution. If z ˉ = 0 \bar{z} = 0 z ˉ = 0 , then (10) and nonnegativity force y ˉ = 0 \bar{y} = 0 y ˉ = 0 , so none of the inequalities below is violated.
Anticlique inequalities
Two nonadjacent vertices cannot belong to the same clique. This gives the pairwise inequalities
y i + y j ≤ 1 ( i , j ∈ U , i ≠ j , { i , j } ∉ F ) , (17) y_i + y_j \le1 \qquad(i,j \in U,\ i \ne j,\ \{i,j\} \notin F), \tag*{(17)} y i + y j ≤ 1 ( i , j ∈ U , i = j , { i , j } ∈ / F ) , (17)
which underlie the standard edge formulation on the complement graph [31 ] . For example, the LP solution in Figure 1 has y 3 + y 4 = 0.84 + 0.60 > 1 y_3 + y_4 = 0.84 + 0.60 > 1 y 3 + y 4 = 0.84 + 0.60 > 1 , although vertices 3 and 4 are nonadjacent. More generally, an anticlique is an independent set S S S of H H H . It gives
y ( S ) ≤ 1 ( S ⊆ U independent in H ) , (18) y(S) \le1 \qquad(S \subseteq U\ \text{independent in } H), \tag*{(18)} y ( S ) ≤ 1 ( S ⊆ U independent in H ) , (18)
the classical clique inequality for the stable set polytope of H ‾ \overline{H} H [24 , 14 ] . The corresponding strengthened forms are
y i + y j ≤ z ( i , j ∈ U , i ≠ j , { i , j } ∉ F ) , (19) y_i + y_j \le z \qquad(i,j \in U,\ i \ne j,\ \{i,j\} \notin F), \tag*{(19)} y i + y j ≤ z ( i , j ∈ U , i = j , { i , j } ∈ / F ) , (19)
y ( S ) ≤ z ( S ⊆ U independent in H ) . (20) y(S) \le z \qquad(S \subseteq U\ \text{independent in } H). \tag*{(20)} y ( S ) ≤ z ( S ⊆ U independent in H ) . (20)
For singleton sets, (20) is already implied by (13) .
Exact separation requires a maximum-weight independent set computation in H H H , with weights y ˉ i \bar{y}_i y ˉ i , and is NP-hard in general. We therefore use a greedy procedure to generate candidate sets. Sort the vertices by nonincreasing y ˉ i \bar{y}_i y ˉ i . For a starting vertex i i i with y ˉ i > 0 \bar{y}_i > 0 y ˉ i > 0 , choose the first subsequent, unmarked vertex j j j that is nonadjacent to i i i ; skip i i i if no such vertex exists. Starting with S = { i , j } S = \{i,j\} S = { i , j } , scan the remaining vertices in this order and add a vertex whenever it is nonadjacent to every vertex already in S S S . The experimental implementation adds (18) when y ˉ ( S ) > 1 \bar{y}(S) > 1 y ˉ ( S ) > 1 and marks the vertices of the accepted set to suppress duplicate candidates within the same separation call. The same candidate-generation procedure separates (20) by using the threshold y ˉ ( S ) > z ˉ \bar{y}(S) > \bar{z} y ˉ ( S ) > z ˉ .
Anticlique inequalities were separated only within the branch-and-bound tree in the reported experiments. The implementation also contains an optional preprocessing routine that seeks large anticliques by solving maximum clique problems on G k G^k G k under a time limit; this routine was disabled in those experiments.
Lifted rank inequalities
Fix an integer a a a with 1 ≤ a ≤ q − 1 1 \le a \le q - 1 1 ≤ a ≤ q − 1 . We construct a set S ⊆ U S \subseteq U S ⊆ U with an insertion order in which each vertex has at most a a a neighbors among its predecessors. A greedy coloring in this order uses at most a + 1 a + 1 a + 1 colors, so ω ( H [ S ] ) ≤ a + 1 \omega(H[S]) \le a + 1 ω ( H [ S ]) ≤ a + 1 and y ( S ) ≤ a + 1 y(S) \le a + 1 y ( S ) ≤ a + 1 is valid. This unlifted inequality is implied by the sum of the anticlique inequalities for the color classes; the sum may be stronger if fewer than a + 1 a + 1 a + 1 colors suffice.
Candidate sets are generated from the same ordering by nonincreasing LP value. For a starting vertex i i i , choose the first subsequent vertex j j j adjacent to i i i and initialise S = { i , j } S = \{i,j\} S = { i , j } ; if no such j j j exists, skip i i i . Scan the remaining vertices and add u u u whenever ∣ N H ( u ) ∩ S ∣ ≤ a |N_H(u) \cap S| \le a ∣ N H ( u ) ∩ S ∣ ≤ a . The initial edge is compatible with this insertion rule because a ≥ 1 a \ge1 a ≥ 1 .
Proposition 3.2 (An independent-set lifting). Let S ⊆ U S \subseteq U S ⊆ U satisfy ω ( H [ S ] ) ≤ a + 1 \omega(H[S]) \le a + 1 ω ( H [ S ]) ≤ a + 1 , where a ≥ 1 a \ge1 a ≥ 1 , and put b i = ∣ N H ( i ) ∩ S ∣ b_i = |N_H(i) \cap S| b i = ∣ N H ( i ) ∩ S ∣ for i ∈ S i \in S i ∈ S . Let L ⊆ { i ∈ S : b i < a } L \subseteq\{i \in S : b_i < a\} L ⊆ { i ∈ S : b i < a } be independent in H H H and define
c i = { a + 1 − b i , i ∈ L , 1 , i ∈ S ∖ L . c_i =
\begin{cases}
a + 1 - b_i, & i \in L,\\
1, & i \in S \setminus L.
\end{cases} c i = { a + 1 − b i , 1 , i ∈ L , i ∈ S ∖ L . Then the lifted rank inequality
∑ i ∈ S c i y i ≤ a + 1 (21) \sum_{i \in S} c_i y_i \le a + 1 \tag*{(21)} i ∈ S ∑ c i y i ≤ a + 1 (21) is valid for every clique of H H H . Consequently,
∑ i ∈ S c i y i ≤ ( a + 1 ) z (22) \sum_{i \in S} c_i y_i \le(a + 1)z \tag*{(22)} i ∈ S ∑ c i y i ≤ ( a + 1 ) z (22) is valid for the fixed-size formulation.
Proof. A clique C C C contains at most one vertex of L L L . If C ∩ L = ∅ C \cap L = \varnothing C ∩ L = ∅ , its left-hand side in (21) is ∣ C ∩ S ∣ ≤ a + 1 |C \cap S| \le a + 1 ∣ C ∩ S ∣ ≤ a + 1 . Otherwise, write C ∩ L = { i } C \cap L = \{i\} C ∩ L = { i } . Every other vertex of C ∩ S C \cap S C ∩ S is a neighbor of i i i in S S S and has coefficient 1. There are at most b i b_i b i such vertices, so the left-hand side is at most ( a + 1 − b i ) + b i = a + 1 (a + 1 - b_i) + b_i = a + 1 ( a + 1 − b i ) + b i = a + 1 . The scaled inequality follows from Proposition 3.1 .
To choose L L L , repeatedly select an eligible vertex i i i that is nonadjacent to all previously selected vertices and maximises ( a − b i ) y ˉ i (a-b_i)\bar{y}_i ( a − b i ) y ˉ i . Stop when no eligible vertex remains. This quantity is the increase in the left-hand side obtained by replacing coefficient 1 1 1 with a + 1 − b i a+1-b_i a + 1 − b i . The construction permits b i = 0 b_i=0 b i = 0 ; such a vertex receives coefficient a + 1 a+1 a + 1 , as required when it is the only selected vertex from S S S . More generally, any certified bound u i ≥ ω ( H [ N H ( i ) ∩ S ] ) u_i \ge\omega(H[N_H(i)\cap S]) u i ≥ ω ( H [ N H ( i ) ∩ S ]) can replace b i b_i b i in the proof; the resulting coefficient improves on 1 1 1 only when u i < a u_i<a u i < a . In particular, the coefficient a + 1 − ω ( H [ N H ( i ) ∩ S ] ) a+1-\omega(H[N_H(i)\cap S]) a + 1 − ω ( H [ N H ( i ) ∩ S ]) is valid and is at least as large as the degree-based coefficient, although computing it exactly requires a further clique computation.
The experimental separation routine repeats the construction for starting vertices with positive LP value and increases a a a from 1 1 1 , subject to a + 1 ≤ q a+1\le q a + 1 ≤ q , until the routine finds no further violated inequality at the current value of a a a . This is a heuristic stopping rule and does not certify that larger values of a a a yield no violated cuts. The same candidates can be tested against (22) by comparing their weighted LP value with ( a + 1 ) z ˉ (a+1)\bar{z} ( a + 1 ) z ˉ . For q = 1 q=1 q = 1 , this family is unnecessary.
Shortest-path inequalities
Shortest paths provide anticliques without an LP solution and therefore give inexpensive preprocessing cuts. Let P = SP G ˉ ( i , j ) P=\operatorname{SP}_{\bar{G}}(i,j) P = SP G ˉ ( i , j ) be any shortest path in the original auxiliary graph, with 2 ≤ dist G ˉ ( i , j ) < ∞ 2\le\operatorname{dist}_{\bar{G}}(i,j)<\infty 2 ≤ dist G ˉ ( i , j ) < ∞ . A shortest path in an unweighted graph is induced: an edge joining nonconsecutive path vertices would produce a shorter path. Consequently, a clique meets P P P in at most two vertices, and
∑ ℓ ∈ P y ℓ ≤ 2 (23) \sum_{\ell\in P} y_\ell\le2 \tag*{(23)} ℓ ∈ P ∑ y ℓ ≤ 2 (23)
is valid. When the working graph has been reduced, variables for deleted vertices are interpreted as zero. The inequality remains valid because the working graph is a subgraph of G ˉ \bar{G} G ˉ . Figure 2 gives the five-vertex example.
Figure 2. A shortest path in the auxiliary graph. Solid lines are edges; dotted lines indicate the absent chords. A clique contains at most two of the displayed vertices.
Writing the vertices of P P P in path order, let S 0 S_0 S 0 and S 1 S_1 S 1 be its two parity classes. Both are independent in G ‾ \overline{G} G , and remain so after any graph reduction. Thus (3.9) is the sum of y ( S 0 ) ≤ 1 y(S_0) \le1 y ( S 0 ) ≤ 1 and y ( S 1 ) ≤ 1 y(S_1) \le1 y ( S 1 ) ≤ 1 . In particular, for a path of length two it follows from the pairwise inequality on the endpoints and the upper bound on the middle vertex. The scaled path inequality is
∑ ℓ ∈ P y ℓ ≤ 2 z , (24) \sum_{\ell\in P} y_{\ell} \le2z, \tag*{(24)} ℓ ∈ P ∑ y ℓ ≤ 2 z , (24)
and it is dominated by the two separate inequalities
y ( S 0 ) ≤ z , y ( S 1 ) ≤ z . (25) y(S_0) \le z,\qquad y(S_1) \le z. \tag*{(25)} y ( S 0 ) ≤ z , y ( S 1 ) ≤ z . (25)
Retaining the parity inequalities therefore gives a formulation at least as strong as retaining only their sum. It uses twice as many rows, with the same total number of coefficients on the y y y -variables. The reported implementation generates the unscaled inequalities (3.9) once, before the first subproblem, using one shortest path per eligible vertex pair and only for instances with ∣ V ∣ ≤ 600 |V| \le600 ∣ V ∣ ≤ 600 . Neither the parity refinement nor the z z z -scaled forms are included in the reported computational results.
Spectral bounds and cuts
We use spectral information in two ways: to bound the target clique size globally and to certify the right-hand sides of rank inequalities on subsets of the working graph. We first recall the bounds and specify the numerical conditions needed for valid certificates. We then describe spectral rank cuts and a further inequality for the fixed-size problem. The strengthened inequalities presented below are distinguished from the forms used in the reported experiments.
Spectral bounds
For a simple graph J J J on n n n vertices, let A A A be its adjacency matrix, with eigenvalues λ 1 ≥ ⋯ ≥ λ n \lambda_1 \ge\cdots\ge\lambda_n λ 1 ≥ ⋯ ≥ λ n . Let D D D be the diagonal matrix of vertex degrees and let δ \delta δ be the minimum degree. The Laplacian L = D − A L = D - A L = D − A has eigenvalues 0 = μ 1 ≤ ⋯ ≤ μ n 0 = \mu_1 \le\cdots\le\mu_n 0 = μ 1 ≤ ⋯ ≤ μ n . When δ ≥ 1 \delta\ge1 δ ≥ 1 , the normalized Laplacian L = I − D − 1 / 2 A D − 1 / 2 \mathcal{L} = I - D^{-1/2}AD^{-1/2} L = I − D − 1/2 A D − 1/2 is defined and has eigenvalues 0 = σ 1 ≤ ⋯ ≤ σ n 0 = \sigma_1 \le\cdots\le\sigma_n 0 = σ 1 ≤ ⋯ ≤ σ n .
Theorem 4.1 (Inertia bound [11 ] ). For a graph J J J on n n n vertices,
α 1 ( J ) ≤ min { ∣ { i : λ i ≥ 0 } ∣ , ∣ { i : λ i ≤ 0 } ∣ } . \alpha_1(J) \le\min\left\{ \left|\{i : \lambda_i \ge0\}\right|,\left|\{i : \lambda_i \le0\}\right| \right\}. α 1 ( J ) ≤ min { ∣ { i : λ i ≥ 0 } ∣ , ∣ { i : λ i ≤ 0 } ∣ } .
Theorem 4.2 (Haemers bound [15 ] ). For a graph J J J on n n n vertices with at least one edge and minimum degree δ \delta δ ,
α 1 ( J ) ≤ n − λ 1 λ n δ 2 − λ 1 λ n . \alpha_1(J) \le n\frac{-\lambda_1\lambda_n}{\delta^2-\lambda_1\lambda_n}. α 1 ( J ) ≤ n δ 2 − λ 1 λ n − λ 1 λ n .
Theorem 4.3 (Godsil–Newman bound [13 ] ). For a graph J J J on n n n vertices with at least one edge and minimum degree δ \delta δ , the largest Laplacian eigenvalue satisfies μ n > 0 \mu_n > 0 μ n > 0 , and
α 1 ( J ) ≤ n μ n − δ μ n . \alpha_1(J) \le n\frac{\mu_n-\delta}{\mu_n}. α 1 ( J ) ≤ n μ n μ n − δ .
Theorem 4.4 (Harant–Richter bound [16 ] ). For a graph J J J on n n n vertices with m m m edges and minimum degree δ ≥ 1 \delta\ge1 δ ≥ 1 ,
α 1 ( J ) ≤ 2 m δ σ n − 1 σ n . \alpha_1(J) \le\frac{2m}{\delta}\frac{\sigma_n-1}{\sigma_n}. α 1 ( J ) ≤ δ 2 m σ n σ n − 1 .
The inertia bound uses the signs of the adjacency eigenvalues. The other three bounds use extremal eigenvalues and all reduce to Hoffman’s bound n ( − λ n ) / ( d − λ n ) n(-\lambda_n)/(d-\lambda_n) n ( − λ n ) / ( d − λ n ) when J J J is d d d -regular with d > 0 d > 0 d > 0 . For an edgeless graph, α 1 ( J ) = n \alpha_1(J) = n α 1 ( J ) = n directly. More generally, if I I I is the set of isolated vertices, then
α 1 ( J ) = ∣ I ∣ + α 1 ( J − I ) . \alpha_1(J)=|I|+\alpha_1(J-I). α 1 ( J ) = ∣ I ∣ + α 1 ( J − I ) .
We may therefore remove isolated vertices before applying the bounds and add their number afterwards; all parameters of a bound on J − I J-I J − I are evaluated on that graph.
A global bound for k k k -MIS The identity α k ( G ) = α 1 ( G k ) = ω ( G ‾ ) \alpha_k(G)=\alpha_1(G^k)=\omega(\overline{G}) α k ( G ) = α 1 ( G k ) = ω ( G ) allows us to apply Theorems 4.1 –4.4 to the original power graph G k G^k G k , before target-dependent reduction of the auxiliary graph. Let I I I be the isolated vertices of G k G^k G k and put J = G k − I J=G^k-I J = G k − I . If J J J is empty, set q max = ∣ V ∣ q_{\max}=|V| q m a x = ∣ V ∣ . Otherwise, let B 1 ( J ) , … , B 4 ( J ) B_1(J),\ldots,B_4(J) B 1 ( J ) , … , B 4 ( J ) be the four bounds above and define, in exact arithmetic,
q max = min { ∣ V ∣ , ∣ I ∣ + min 1 ≤ j ≤ 4 B j ( J ) } . (26) q_{\max}=\min\left\{|V|,\ |I|+\min_{1\le j\le4}B_j(J)\right\}. \tag*{(26)} q m a x = min { ∣ V ∣ , ∣ I ∣ + 1 ≤ j ≤ 4 min B j ( J ) } . (26)
This is an integer upper bound on α k ( G ) \alpha_k(G) α k ( G ) . Bounds based directly on the spectrum of G G G , including polynomial inertia-type and ratio-type bounds [1 , 2 , 3 , 4 ] , can be incorporated by taking the minimum with any additional certified upper bound. Their computation and their effect on the algorithm are separate from the four-bound construction in (26) .
Numerical certification The validity of a spectral cut or stopping bound depends on the direction of its numerical error. The following conditions provide sufficient certificates; they are theoretical requirements and do not assert that the reported runs were validated by interval computations. Here all spectra and graph parameters refer to the graph being bounded, so n = ∣ V ( J ) ∣ n=|V(J)| n = ∣ V ( J ) ∣ when isolated vertices have been removed.
Suppose intervals [ a i , b i ] [a_i,b_i] [ a i , b i ] enclose the adjacency eigenvalues, counted with multiplicity. Then
B i n + ( J ) : = min { ∣ { i : b i ≥ 0 } ∣ , ∣ { i : a i ≤ 0 } ∣ } (27) B_{\mathrm{in}}^{+}(J):=\min\left\{\left|\{i:b_i\ge0\}\right|,\ \left|\{i:a_i\le0\}\right|\right\} \tag*{(27)} B in + ( J ) := min { ∣ { i : b i ≥ 0 } ∣ , ∣ { i : a i ≤ 0 } ∣ } (27)
is a valid inertia upper bound. Indeed, every nonnegative eigenvalue is counted in the first set and every nonpositive eigenvalue in the second; an interval containing zero is conservatively counted in both. In particular, the usual sign-tolerance rule is valid when the tolerance is a certified bound on every eigenvalue error.
For the ratio bounds, suppose positive numbers u u u , v v v , M M M , S S S satisfy
λ 1 ≤ u , − λ n ≤ v , μ n ≤ M , σ n ≤ S . \lambda_1 \le u,\qquad-\lambda_n \le v,\qquad\mu_n \le M,\qquad\sigma_n \le S. λ 1 ≤ u , − λ n ≤ v , μ n ≤ M , σ n ≤ S .
Under the respective theorem hypotheses, conservative upper bounds are
n u v δ 2 + u v , n ( 1 − δ M ) , 2 m δ ( 1 − 1 S ) . (28) \frac{nuv}{\delta^2+uv},\qquad n\left(1-\frac{\delta}{M}\right),\qquad\frac{2m}{\delta}\left(1-\frac{1}{S}\right). \tag*{(28)} δ 2 + uv n uv , n ( 1 − M δ ) , δ 2 m ( 1 − S 1 ) . (28)
For the first expression, − λ 1 λ n ≤ u v -\lambda_1\lambda_n \le uv − λ 1 λ n ≤ uv and t ↦ n t / ( δ 2 + t ) t \mapsto nt/(\delta^2+t) t ↦ n t / ( δ 2 + t ) is nondecreasing for t > 0 t>0 t > 0 . The other two expressions are nondecreasing in the positive arguments M M M and S S S . Evaluating these expressions with outward rounding and using the upper endpoint of each resulting enclosure therefore preserves validity. Integer rounding is applied only after this upper endpoint has been obtained. An uncertified candidate may be omitted without affecting the validity of the remaining bounds.
A fixed additive guard on the final bound is not a substitute for this calculation. For example, the convention of treating eigenvalues within 10 − 4 10^{-4} 1 0 − 4 of zero as zero and rounding a computed ratio bound β ^ \widehat{\beta} β to ⌊ β ^ + 0.01 ⌋ \lfloor\widehat{\beta}+0.01\rfloor ⌊ β + 0.01 ⌋ does not by itself certify the latter bound. A matching on 1000 vertices has α 1 = 500 \alpha_1=500 α 1 = 500 and σ n = 2 \sigma_n=2 σ n = 2 . Substituting σ ^ n = 1.99991 \widehat{\sigma}_n=1.99991 σ n = 1.99991 in Theorem 4.4 gives β ^ ≈ 499.977499 \widehat{\beta}\approx499.977499 β ≈ 499.977499 and hence ⌊ β ^ + 0.01 ⌋ = 499 \lfloor\widehat{\beta}+0.01\rfloor=499 ⌊ β + 0.01 ⌋ = 499 , despite an eigenvalue error smaller than 10 − 4 10^{-4} 1 0 − 4 . Certification is required for every spectral cut used in a proof, as well as for a global bound used to terminate the search; validating only the final stopping bound does not validate earlier cuts.
Spectral bound inequalities
Fix a target size q q q and let H = ( U , F ) H=(U,F) H = ( U , F ) be the current working auxiliary graph. After peeling, H = H q H=H_q H = H q in the notation of § 2.3 . Let ( y ˉ , z ˉ ) (\bar{y},\bar{z}) ( y ˉ , z ˉ ) be the current LP solution, and order U U U as π 1 , … , π ∣ U ∣ \pi_1,\ldots,\pi_{|U|} π 1 , … , π ∣ U ∣ so that y ˉ π 1 ≥ ⋯ ≥ y ˉ π ∣ U ∣ \bar{y}_{\pi_1}\ge\cdots\ge\bar{y}_{\pi_{|U|}} y ˉ π 1 ≥ ⋯ ≥ y ˉ π ∣ U ∣ . For 2 ≤ ℓ ≤ ∣ U ∣ 2\le\ell\le|U| 2 ≤ ℓ ≤ ∣ U ∣ , put
W ℓ = { π 1 , … , π ℓ } , G ~ ℓ = H [ W ℓ ] ‾ , W_\ell=\{\pi_1,\ldots,\pi_\ell\},\qquad\widetilde{G}_\ell=\overline{H[W_\ell]}, W ℓ = { π 1 , … , π ℓ } , G ℓ = H [ W ℓ ] ,
and let A ℓ A_\ell A ℓ be the adjacency matrix of G ~ ℓ \widetilde{G}_\ell G ℓ . The complement here is taken within W ℓ W_\ell W ℓ . Before edge peeling, G ~ ℓ = G k [ W ℓ ] \widetilde{G}_\ell=G^k[W_\ell] G ℓ = G k [ W ℓ ] ; after peeling this equality need not hold.
The intersection of a clique of H H H with W ℓ W_\ell W ℓ has size at most α 1 ( G ~ ℓ ) \alpha_1(\widetilde{G}_\ell) α 1 ( G ℓ ) . Thus any upper bound on this independence number gives a rank inequality for the stable set polytope of H ‾ \overline{H} H [9 , 26 , 25 ] . Using the inertia bound, define
β ℓ : = min { ∣ { i : λ i ( A ℓ ) ≥ 0 } ∣ , ∣ { i : λ i ( A ℓ ) ≤ 0 } ∣ } ≥ α 1 ( G ~ ℓ ) . (29) \beta_\ell:=\min\left\{\left|\{i:\lambda_i(A_\ell)\ge0\}\right|,\left|\{i:\lambda_i(A_\ell)\le0\}\right|\right\}\ge\alpha_1(\widetilde{G}_\ell). \tag*{(29)} β ℓ := min { ∣ { i : λ i ( A ℓ ) ≥ 0 } ∣ , ∣ { i : λ i ( A ℓ ) ≤ 0 } ∣ } ≥ α 1 ( G ℓ ) . (29)
The resulting spectral rank cut is
∑ i = 1 ℓ y π i ≤ β ℓ . (30) \sum_{i=1}^{\ell}y_{\pi_i}\le\beta_\ell. \tag*{(30)} i = 1 ∑ ℓ y π i ≤ β ℓ . (30)
When exact inertia is unavailable, β ℓ \beta_\ell β ℓ in a cut is replaced by a certified integer upper bound such as (27) .
We strengthen this spectral rank cut for the fixed-size formulation to
∑ i = 1 ℓ y π i ≤ β ℓ z . (31) \sum_{i=1}^{\ell} y_{\pi_i} \le\beta_\ell z. \tag*{(31)} i = 1 ∑ ℓ y π i ≤ β ℓ z . (31)
At an integer feasible solution, z = 0 z=0 z = 0 forces y = 0 y=0 y = 0 , while z = 1 z=1 z = 1 selects a q q q -clique; these are the only possibilities even when z z z is declared continuous, as shown in § 2 . Hence (31) is valid. Since 0 ≤ z ≤ 1 0 \le z \le1 0 ≤ z ≤ 1 , it dominates (30) . The reported spectral rank cuts use the unscaled form (30) ; the computational effect of (31) has not been measured in those experiments.
The inertia certificate can improve on a coloring certificate. For example, when G ~ ℓ = C 5 \widetilde{G}_\ell= C_5 G ℓ = C 5 , its inertia bound is 2 2 2 whereas χ ( C ‾ 5 ) = 3 \chi(\overline{C}_5)=3 χ ( C 5 ) = 3 . Such an improvement is not implied by symmetry alone. The Lovász theta number of G ~ ℓ \widetilde{G}_\ell G ℓ provides another upper bound on its independence number [21 ] . A certified theta bound could be combined with inertia by taking their minimum, but would require a semidefinite optimization step; neither certificate uniformly dominates the other.
Separation and pruning. Write s ℓ = ∑ i = 1 ℓ y ˉ π i s_\ell= \sum_{i=1}^{\ell} \bar{y}_{\pi_i} s ℓ = ∑ i = 1 ℓ y ˉ π i . The unscaled cut is violated when s ℓ > β ℓ s_\ell> \beta_\ell s ℓ > β ℓ . A dense eigendecomposition of A ℓ A_\ell A ℓ requires O ( ℓ 3 ) O(\ell^3) O ( ℓ 3 ) arithmetic operations, so checking every prefix independently costs O ( ∣ U ∣ 4 ) O(|U|^4) O ( ∣ U ∣ 4 ) operations per separation call. The separator therefore uses filters to reduce the number of decompositions.
One filter skips a prefix when y ˉ π ℓ − 1 + y ˉ π ℓ ≤ 1 \bar{y}_{\pi_{\ell-1}}+\bar{y}_{\pi_\ell}\le1 y ˉ π ℓ − 1 + y ˉ π ℓ ≤ 1 . This is a heuristic and does not certify nonviolation. For example, let H H H consist of a C 5 C_5 C 5 and an additional vertex adjacent to all five cycle vertices, and take q = 3 q=3 q = 3 . This graph survives the reduction rules. Assigning LP value 1 / 2 1/2 1/2 to each cycle vertex, zero to the additional vertex, and z ˉ = 5 / 6 \bar{z}=5/6 z ˉ = 5/6 gives a feasible point of the base LP. The cycle vertices form a prefix with s 5 = 5 / 2 > β 5 = 2 s_5=5/2>\beta_5=2 s 5 = 5/2 > β 5 = 2 , since C ‾ 5 ≅ C 5 \overline{C}_5\cong C_5 C 5 ≅ C 5 , but the test skips it.
An exact pruning rule follows from interlacing. Since A ℓ A_\ell A ℓ is a principal submatrix of A ℓ + 1 A_{\ell+1} A ℓ + 1 , Cauchy interlacing implies that the latter has at least as many nonnegative eigenvalues and at least as many nonpositive eigenvalues as the former. Consequently,
β ℓ + 1 ≥ β ℓ . \beta_{\ell+1} \ge\beta_\ell. β ℓ + 1 ≥ β ℓ .
Once β ℓ \beta_\ell β ℓ is known exactly, a later prefix j > ℓ j>\ell j > ℓ cannot violate (30) while s j ≤ β ℓ s_j\le\beta_\ell s j ≤ β ℓ . Computations may therefore be postponed until the first later prefix whose mass exceeds this value. Independently computed conservative upper bounds on the inertia values need not be monotone. If exact values are unavailable, this safe pruning test instead requires a certified lower bound on β ℓ \beta_\ell β ℓ ; using an arbitrary upper bound gives only a heuristic filter. Skipping a cut heuristically affects separation strength, not the validity of cuts actually added.
Two further comparisons avoid retaining unnecessary cuts. If ℓ < ∣ U ∣ \ell<|U| ℓ < ∣ U ∣ and β ℓ = β ℓ + 1 \beta_\ell=\beta_{\ell+1} β ℓ = β ℓ + 1 , the cut for ℓ + 1 \ell+1 ℓ + 1 dominates the cut for ℓ \ell ℓ by nonnegativity. Also, if ℓ 1 < ℓ \ell_1<\ell ℓ 1 < ℓ and
s ℓ − s ℓ 1 ≤ β ℓ − β ℓ 1 , s_\ell-s_{\ell_1}\le\beta_\ell-\beta_{\ell_1}, s ℓ − s ℓ 1 ≤ β ℓ − β ℓ 1 ,
then s ℓ 1 − β ℓ 1 ≥ s ℓ − β ℓ s_{\ell_1}-\beta_{\ell_1} \ge s_{\ell}-\beta_{\ell} s ℓ 1 − β ℓ 1 ≥ s ℓ − β ℓ : the earlier cut has at least as much violation at the current LP point. The latter comparison is not a polyhedral dominance statement. A cut is discarded in favor of another only when the preferred inequality is retained or already present. With numerical certificates, these two comparisons use the actual right-hand sides of the certified cuts.
For the strengthened family (31) , violation is tested against β ℓ z ˉ \beta_{\ell}\bar{z} β ℓ z ˉ . The safe prefix test becomes s j ≤ β ℓ z ˉ s_j \le\beta_{\ell}\bar{z} s j ≤ β ℓ z ˉ , and the comparison of current violations becomes
s ℓ − s ℓ 1 ≤ ( β ℓ − β ℓ 1 ) z ˉ . s_{\ell}-s_{\ell_1} \le(\beta_{\ell}-\beta_{\ell_1})\bar{z}. s ℓ − s ℓ 1 ≤ ( β ℓ − β ℓ 1 ) z ˉ .
The same certification qualifications apply. In particular, the unscaled pruning threshold cannot be used as a nonviolation certificate for the scaled family when z ˉ < 1 \bar{z}<1 z ˉ < 1 .
Extension and lifting. Suppose a set W ⊆ U W \subseteq U W ⊆ U has a certified integer bound r ≥ ω ( H [ W ] ) r \ge\omega(H[W]) r ≥ ω ( H [ W ]) . A vertex outside W W W may be added if it has at most r − 1 r-1 r − 1 neighbors in the current set. Every clique containing the added vertex then has size at most r r r , while cliques not containing it already satisfy the bound. Applying this argument after each insertion preserves ω ( H [ W ] ) ≤ r \omega(H[W]) \le r ω ( H [ W ]) ≤ r . Candidates may be considered in nonincreasing LP order.
The coefficient lifting of § 3.2 also applies with right-hand side r r r . Specifically, for a pairwise nonadjacent set of lifted vertices in W W W , a vertex i i i with d i = ∣ N H ( i ) ∩ W ∣ < r − 1 d_i=|N_H(i)\cap W|<r-1 d i = ∣ N H ( i ) ∩ W ∣ < r − 1 may receive coefficient r − d i r-d_i r − d i , while all unlifted coefficients remain 1 1 1 . A clique contains at most one lifted vertex; if it contains i i i , the remaining contribution is at most d i d_i d i , so the total is at most r r r . If it contains none, its contribution is its cardinality, also at most r r r . The resulting inequality may again be strengthened by replacing its right-hand side r r r with r z rz r z .
Non-selected vertex inequalities
This family exploits a different implication of the fixed target size: a q q q -clique containing sufficiently many vertices of a chosen set may have to use vertices outside the support of the current LP solution. For any T ⊆ U T \subseteq U T ⊆ U , write y ( T ) = ∑ i ∈ T y i y(T)=\sum_{i\in T}y_i y ( T ) = ∑ i ∈ T y i .
For each integer 1 ≤ a ≤ q − 1 1 \le a \le q-1 1 ≤ a ≤ q − 1 , scan the vertices with 0 < y ˉ i < 1 0<\bar{y}_i<1 0 < y ˉ i < 1 in nonincreasing LP order and let S S S be the first prefix with y ˉ ( S ) > a \bar{y}(S)>a y ˉ ( S ) > a . If their total mass is at most a a a , skip this value of a a a . A vertex with y ˉ i = 1 \bar{y}_i=1 y ˉ i = 1 need not be included in the candidate set: the base neighborhood constraint requires neighbor mass at least q − 1 q-1 q − 1 , while the cardinality equation and z ˉ ≤ 1 \bar{z}\le1 z ˉ ≤ 1 leave at most q − 1 q-1 q − 1 mass outside i i i . Thus z ˉ = 1 \bar{z}=1 z ˉ = 1 and every other vertex with positive LP value is adjacent to i i i .
Obtain a certified integer bound b ≥ ω ( H [ S ] ) b \ge\omega(H[S]) b ≥ ω ( H [ S ]) , for example from the inertia of H [ S ] H[S] H [ S ] . Since S S S is nonempty, b ≥ 1 b \ge1 b ≥ 1 . Continue only when b ≤ a b \le a b ≤ a , and define
P = { i ∈ U ∖ S : y ˉ i > 0 , ∣ N H ( i ) ∩ S ∣ ≥ b } , P=\{i\in U\setminus S:\bar{y}_i>0,\ |N_H(i)\cap S|\ge b\}, P = { i ∈ U ∖ S : y ˉ i > 0 , ∣ N H ( i ) ∩ S ∣ ≥ b } ,
R = { i ∈ U ∖ S : y ˉ i = 0 , ∣ N H ( i ) ∩ S ∣ ≥ b } . R=\{i\in U\setminus S:\bar{y}_i=0,\ |N_H(i)\cap S|\ge b\}. R = { i ∈ U ∖ S : y ˉ i = 0 , ∣ N H ( i ) ∩ S ∣ ≥ b } .
Let c ≥ ω ( H [ P ] ) c \ge\omega(H[P]) c ≥ ω ( H [ P ]) be a certified integer bound computed on the entire set P P P , with c = 0 c = 0 c = 0 for P = ∅ P = \varnothing P = ∅ and c = 1 c = 1 c = 1 for ∣ P ∣ = 1 |P| = 1 ∣ P ∣ = 1 . If q ≤ b + c q \le b + c q ≤ b + c , no cut of the following form is generated.
Proposition 4.5. Under the preceding assumptions, if q > b + c q > b + c q > b + c , the inequality
( y ( S ) − ( b − 1 ) z ) ( q − b − c ) ≤ y ( R ) (32) \bigl(y(S) - (b - 1)z\bigr)(q - b - c) \le y(R) \tag*{(32)} ( y ( S ) − ( b − 1 ) z ) ( q − b − c ) ≤ y ( R ) (32) is valid for the integer feasible solutions of the fixed-size formulation.
Proof. If z = 0 z = 0 z = 0 , the cardinality equation and nonnegativity force y = 0 y = 0 y = 0 , so both sides are zero. Otherwise z = 1 z = 1 z = 1 , and the selected vertices form a q q q -clique C C C in H H H . The bound on H [ S ] H[S] H [ S ] gives ∣ C ∩ S ∣ ≤ b |C \cap S| \le b ∣ C ∩ S ∣ ≤ b . If ∣ C ∩ S ∣ ≤ b − 1 |C \cap S| \le b - 1 ∣ C ∩ S ∣ ≤ b − 1 , the left-hand side is nonpositive and the inequality follows from y ( R ) ≥ 0 y(R) \ge0 y ( R ) ≥ 0 .
If ∣ C ∩ S ∣ = b |C \cap S| = b ∣ C ∩ S ∣ = b , every vertex of C ∖ S C \setminus S C ∖ S is adjacent to these b b b vertices and therefore lies in P ∪ R P \cup R P ∪ R . At most c c c selected vertices belong to P P P . Hence ∣ C ∩ R ∣ ≥ q − b − c |C \cap R| \ge q - b - c ∣ C ∩ R ∣ ≥ q − b − c , which is precisely (32) in this case.
The corresponding unscaled inequality is
( y ( S ) − b + 1 ) ( q − b − c ) ≤ y ( R ) . (33) \bigl(y(S) - b + 1\bigr)(q - b - c) \le y(R). \tag*{(33)} ( y ( S ) − b + 1 ) ( q − b − c ) ≤ y ( R ) . (33)
It follows from (32) because b ≥ 1 b \ge1 b ≥ 1 and z ≤ 1 z \le1 z ≤ 1 ; the difference between their left-hand sides is ( b − 1 ) ( 1 − z ) ( q − b − c ) ≥ 0 (b - 1)(1 - z)(q - b - c) \ge0 ( b − 1 ) ( 1 − z ) ( q − b − c ) ≥ 0 . We thus obtain a scaled inequality that is at least as strong throughout the LP domain. Under the separation condition b ≤ a < y ˉ ( S ) b \le a < \bar{y}(S) b ≤ a < y ˉ ( S ) , the ordinary rank cut y ( S ) ≤ b y(S) \le b y ( S ) ≤ b is already violated and can also be added.
The requirement that c c c bound the clique number of the full set P P P is essential. A bound c 0 c_0 c 0 computed on a restricted set P 0 ⊆ P P_0 \subseteq P P 0 ⊆ P can be extended safely by taking c = c 0 + ∣ P ∖ P 0 ∣ c = c_0 + |P \setminus P_0| c = c 0 + ∣ P ∖ P 0 ∣ , since every clique uses at most c 0 c_0 c 0 vertices of P 0 P_0 P 0 and at most ∣ P ∖ P 0 ∣ |P \setminus P_0| ∣ P ∖ P 0 ∣ others. Using c 0 c_0 c 0 alone is not justified.
The reported experiments use the earlier inequality
( y ( S ) − b ) ( q − b − c ) ≤ y ( R ) , q > b + c , (34) \bigl(y(S) - b\bigr)(q - b - c) \le y(R), \qquad q > b + c, \tag*{(34)} ( y ( S ) − b ) ( q − b − c ) ≤ y ( R ) , q > b + c , (34)
rather than (33) or (32) . In the presence of the rank cut y ( S ) ≤ b y(S) \le b y ( S ) ≤ b , (34) is redundant: its left-hand side is nonpositive and its right-hand side is nonnegative. The corrected and scaled forms above are analytical improvements whose computational effect is not established by those experiments.
Solution procedure
We solve a sequence of fixed-size clique problems on the auxiliary graph G ˉ = G ˉ k \bar{G} = \bar{G}^{k} G ˉ = G ˉ k . Starting with q = 1 q = 1 q = 1 , it searches for a clique of size q q q , increases the target after a successful search, and stops when it establishes that the next target is unattainable or reaches a valid upper bound q max q_{\max} q m a x . This order favors successful feasibility searches before the first unsuccessful target. Its computational motivation is the concentration of effort near that target observed in § 6.3 ; it is not a worst-case advantage over binary search.
For each target q ≥ 2 q \ge2 q ≥ 2 , the reduction of § 2.3 produces H q = ( V q , E q ) H_q = (V_q, E_q) H q = ( V q , E q ) . The fixed-size model is then constructed on H q H_q H q . A feasible solution selecting q q q vertices attains the model’s upper objective bound q q q , so the search advances as soon as such a solution is found. If graph reduction rules out a q q q -clique, or the solver establishes optimal objective value zero, the previous successful target gives α k ( G ) = q − 1 \alpha_k(G) = q - 1 α k ( G ) = q − 1 . Alternatively, finding a clique of size q max q_{\max} q m a x gives α k ( G ) = q max \alpha_k(G) = q_{\max} α k ( G ) = q m a x . The fixed-size model itself remains feasible at the zero solution throughout.
Separation and cut reuse. Shortest-path inequalities are generated during preprocessing in the unreduced auxiliary graph and are retained when the target increases. At separation callbacks, vertices are sorted by nonincreasing current LP value, and the procedures of § 3 and § 4 search for violated cuts. Completeness of these separation procedures is unnecessary: the base integer model is already exact, and valid cuts improve its relaxation without removing feasible cliques.
Rank inequalities and their liftings can also be carried from one target to the next. The reductions are monotone in the target: for q ′ > q q' > q q ′ > q , the graph H q ′ H_{q'} H q ′ is a subgraph of H q H_q H q . An inequality valid for every clique of H q H_q H q therefore remains valid on H q ′ H_{q'} H q ′ , with variables for deleted vertices fixed to zero. The same argument justifies reusing the strengthened inequalities with a right-hand side multiplied by z z z : at z = 0 z = 0 z = 0 all selected-vertex variables vanish, and at z = 1 z = 1 z = 1 the underlying clique inequality applies. The non-selected-vertex inequalities depend explicitly on q q q and must instead be regenerated for the new target.
Theorem 5.1 (Correctness of the sequential framework). Let G G G be a nonempty graph and let q max ∈ { 1 , … , ∣ V ∣ } q_{\max} \in\{1, \ldots, |V|\} q m a x ∈ { 1 , … , ∣ V ∣ } satisfy α k ( G ) ≤ q max \alpha_k(G) \le q_{\max} α k ( G ) ≤ q m a x . Suppose that, at each target q q q , the reduction preserves every q q q -clique of G ˉ \bar{G} G ˉ , and every added inequality is valid for the empty solution and for the incidence vector of each such surviving clique. If each fixed-size subproblem is solved to optimality, the sequential framework returns α k ( G ) \alpha_k(G) α k ( G ) . Complete separation of any cut family is not required. If a subproblem is interrupted, the last clique found supplies a valid lower bound.
Proof. Consider a nonzero feasible solution of the fixed-size model, with binary y y y and 0 ≤ z ≤ 1 0 \le z \le1 0 ≤ z ≤ 1 . For any selected vertex, (2.3b) requires at least q − 1 q - 1 q − 1 selected neighbors. Thus at least q q q vertices are selected, whereas (2.3c) allows at most q q q . Exactly q q q vertices are therefore selected, z = 1 z = 1 z = 1 , and every selected vertex is adjacent to all the others. Conversely, the incidence vector of a q q q -clique, together with z = 1 z = 1 z = 1 , satisfies the base model and, by hypothesis, every added inequality. Reduction preserves these cliques. Hence the fixed-size optimum is q q q if a q q q -clique exists in G ˉ \bar{G} G ˉ , and zero otherwise.
If the first zero optimum occurs at target q q q , a clique of size q − 1 q - 1 q − 1 has already been found. No larger clique exists, since every clique of size at least q q q contains a q q q -clique. The optimum is therefore q − 1 q - 1 q − 1 . If every target through q max q_{\max} q m a x succeeds, the clique of size q max q_{\max} q m a x meets the valid upper bound. In either case the returned value equals ω ( G ˉ ) = α k ( G ) \omega(\bar{G}) = \alpha_k(G) ω ( G ˉ ) = α k ( G ) . An interrupted search does not invalidate a previously found clique.
The theorem separates the mathematical framework from its numerical implementation. Spectral bounds and spectral cut coefficients must meet the certification conditions of § 4.1 for the theorem to provide an exact certificate. A feasible clique can be checked directly from its vertex set; certifying a successful stopping decision also requires valid upper bounds and cuts throughout the run.
Computational variant evaluated below The experiments use the earlier implementation of this framework: z z z is declared binary, the redundant rows (14) are retained, and cuts use their unscaled right-hand sides. The dynamically separated inequalities are (18) , (21) , (30) , and the weaker non-selected-vertex inequality (34) . The corrected inequality (33) , its strengthened form (32) , the strengthened spectral cuts (31) , and the analogous z z z -scaled combinatorial cuts are not evaluated in those runs. Large-anticlique preprocessing is disabled, and shortest-path preprocessing is used only when ∣ V ∣ ≤ 600 |V| \le600 ∣ V ∣ ≤ 600 .
Within each subproblem, a family is disabled after its separation counter reaches 100. The counter increases by one at a callback that finds no violated inequality of that family and decreases by ten when a violated inequality is found. Rank cuts from previous targets are retained; target-dependent non-selected-vertex inequalities are not. If the time limit is reached without a q q q -clique or a nonexistence conclusion, the run stops with the lower bound from its last successful target.
Computational results
We evaluate the computational variant described above on three benchmark classes for k ∈ { 1 , 2 , 3 , 4 } k \in\{1,2,3,4\} k ∈ { 1 , 2 , 3 , 4 } . We report solution statuses and lower bounds, examine how work is distributed over target sizes, and compare the tested cut configurations. We also compare the method with the discretized integer programming formulation of Martins [22 ] . The conventions below specify how the recorded numerical outcomes relate to the exact framework.
Benchmark instances and experimental conventions
Named graphs The first class contains 79 named graphs from SageMath’s graph library [28 ] , including the Petersen, Coxeter, and Hoffman–Singleton graphs. Their orders range from 4 to 600; the complete list is in Table 1 .
Table 1. Named graph instances, ordered by ∣ V ∣ |V| ∣ V ∣ . Runtimes are in seconds, rounded down. An asterisk indicates solver-reported optimality under the numerical-status convention of § 6.1 ; unstarred values are reported lower bounds.
Coding-theoretic graphs The second class contains 32 graphs from Sloane’s challenge on independent sets [27 ] . The prefixes 1dc.* and 2dc.* denote single- and double-deletion-correcting codes; 1tc.* denotes single-transposition-correcting codes; 1et.* adds end-around transposition; and 1zc.* denotes Z Z Z -channel codes. The suffix gives the number of vertices. Independence in these graphs represents the corresponding code constraint, and increasing k k k imposes additional graph-distance separation.
Sum-rank-metric graphs The third class contains 25 sum-rank-metric graphs from Abiad, Khramova, and Ravagnani [4 ] . For a prime power q q q and tuples n = ( n 1 , … , n t ) n=(n_1,\ldots,n_t) n = ( n 1 , … , n t ) and m = ( m 1 , … , m t ) m=(m_1,\ldots,m_t) m = ( m 1 , … , m t ) of positive integers, the vertices are tuples ( X 1 , … , X t ) (X_1,\ldots,X_t) ( X 1 , … , X t ) with X i ∈ F q n i × m i X_i\in\mathbb{F}_q^{n_i\times m_i} X i ∈ F q n i × m i . Two vertices are adjacent when their difference has rank one in exactly one block and is zero in all other blocks. Graph distance equals sum-rank distance, so a k k k -independent set is a code of minimum sum-rank distance at least k + 1 k+1 k + 1 . These graphs have
∣ V ∣ = q ∑ i = 1 t n i m i , ∣ E ∣ = ∣ V ∣ 2 ( q − 1 ) ∑ i = 1 t ( q n i − 1 ) ( q m i − 1 ) . |V|=q^{\sum_{i=1}^{t}n_i m_i},\qquad|E|=\frac{|V|}{2(q-1)}\sum_{i=1}^{t}(q^{n_i}-1)(q^{m_i}-1). ∣ V ∣ = q ∑ i = 1 t n i m i , ∣ E ∣ = 2 ( q − 1 ) ∣ V ∣ i = 1 ∑ t ( q n i − 1 ) ( q m i − 1 ) .
The field-size symbol q q q in these instance descriptions is unrelated to the target clique size. Table 3 lists the parameters explicitly. The Hamming graph is the special case n i = m i = 1 n_i=m_i=1 n i = m i = 1 for every i i i ; none of the listed instances has all blocks of this form.
Table 3. Sum-rank-metric instances, identified by t t t , q q q , n n n , m m m as in § 6.1 . The symbols n , m n,m n , m denote tuples here. Runtimes are in seconds, rounded down. An asterisk indicates solver-reported optimality; † identifies a single-family result and its runtime. The symbol § identifies an unstarred entry whose value is known to be exact from [4 ] .
Computing environment and limits The reported implementation uses C++ with Visual Studio 2017, version 15.9.8, and IBM ILOG CPLEX Optimization Studio 12.9. The runs use one thread on an AMD Ryzen Threadripper 3990X processor at 2.9 GHz with 256 GB of RAM. Each fixed-target MIP solve has a three-hour time limit. Total runtime includes successive target searches and preprocessing, and can therefore substantially exceed three hours.
Numerical status An asterisk in the tables denotes solver-reported optimality for the indicated implementation. For the sequential method, the run terminated with a reported zero optimum at the next target or with a clique attaining its computed upper bound q max q_{\max} q m a x ; for DF, it records the MIP solver’s optimal status. For the configurations using spectral information, rigorous eigenvalue enclosures and a complete audit of the spectral cuts are not available for these runs. The tables therefore distinguish computationally reported optimality from independently certified exact values. The numerical safeguards and certification requirements in § 4.1 apply to both global bounds and generated cuts. Values established in the literature are identified separately where relevant.
Table conventions Tables 1–3 primarily report the configuration with both cut families, denoted Both. Three entries replace an unresolved Both result by a successful single-family result; these entries carry † and use that single-family run’s time. A dagger thus records an additional observed success, not the runtime of a prescribed portfolio. For an unstarred entry, the reported lower bound is the largest obtained by Both for any k ′ ≥ k k' \ge k k ′ ≥ k on the same graph, using α k ( G ) ≥ α k ′ ( G ) \alpha_k(G)\ge\alpha_{k'}(G) α k ( G ) ≥ α k ′ ( G ) . The displayed time remains that of the run at k k k , and need not be the time at which the transferred bound was found. Main-table times are rounded down to whole seconds. Appendix § 10 reports each configuration’s own values without this transfer across k k k , with times rounded to the nearest second.
Solution status and lower bounds
The three main benchmark classes give 544 instance–k k k combinations. Both reports optimality for 470 of them (86.4%). Including the three additional single-family successes increases the union to 473 (86.9%). Among the 416 combinations with at most 256 vertices, these counts are 414 (99.5%) and 415 (99.8%), respectively. These percentages use the numerical-status convention of § 6.1 .
For the named graphs, Both reports optimality on 313 of 316 combinations. All graphs with at most 100 vertices finish within seconds for every tested k k k . The three unresolved combinations are Cell120 at k = 1 , 3 , 4 k = 1, 3, 4 k = 1 , 3 , 4 ; the k = 2 k = 2 k = 2 run returns a starred value of 120 in 645 seconds.
For the coding-theoretic graphs, all combinations with at most 128 vertices are starred. At 256 vertices, the only unresolved Both run is 1et.256 at k = 1 k = 1 k = 1 ; the combinatorial configuration supplies the dagger-marked value 50. Larger instances distinguish the graph families and target distances. For example, several 2dc.* combinations remain tractable as the order increases, whereas many larger instances from the other families retain only lower bounds.
For the sum-rank-metric graphs, all but one combination with at most 256 vertices are starred; the exception has t = 7 t = 7 t = 7 and k = 2 k = 2 k = 2 . At 512 vertices, all six k = 1 k = 1 k = 1 combinations are starred, but seven of the eighteen combinations with k ≥ 2 k \ge2 k ≥ 2 are unresolved. All four combinations at 729 vertices are starred. At 1024 vertices, k = 1 , 2 k = 1, 2 k = 1 , 2 are starred for Both and k = 4 k = 4 k = 4 is supplied by the spectral-only configuration. At orders at least 2048, the only starred result comes from the combinatorial-only configuration at k = 1 k = 1 k = 1 on the 2048-vertex instance. Thus neither the effect of increasing k k k nor the role of graph order is uniform across the benchmark classes.
The reported values agree with the overlapping exact values for named graphs in [3 Table 2] and for sum-rank-metric graphs in [4 Tables 1–2] . In particular, two entries that remain unstarred in our runs are known exactly from the latter source: α 2 = 18 \alpha_2 = 18 α 2 = 18 for t = 3 t = 3 t = 3 , q = 2 q = 2 q = 2 , n = m = ( 2 , 2 , 1 ) n = m = (2,2,1) n = m = ( 2 , 2 , 1 ) , and α 3 = 9 \alpha_3 = 9 α 3 = 9 for t = 6 t = 6 t = 6 , q = 2 q = 2 q = 2 , n = m = ( 2 , 1 5 ) n = m = (2,1^5) n = m = ( 2 , 1 5 ) . They are marked {sup}§ in {xref}Table 3`. Agreement with previously established values provides a consistency check; it does not replace verification of the other numerical conclusions.
Table 2.
Table 7.
Runtime profile across subproblems
Table 4 gives the recorded target-by-target profile for 1et.512. It illustrates the distinction between finding a clique at a feasible target and excluding the next target. For an interrupted run, the largest clique found remains a lower bound rather than a determined value of α k \alpha_k α k .
Table 4. Per-target runtimes for 1et.512 (∣ V ∣ = 512 \lvert V\rvert= 512 ∣ V ∣ = 512 , ∣ E ∣ = 4032 \lvert E\rvert= 4032 ∣ E ∣ = 4032 ). A range denotes targets with similar runtimes; only selected targets are shown for k = 1 k = 1 k = 1 . The q = 1 q = 1 q = 1 time includes preprocessing. For k = 2 , 3 , 4 k = 2, 3, 4 k = 2 , 3 , 4 , the final target has solver-reported nonexistence of a q q q -clique, giving the starred value q − 1 q-1 q − 1 under § 6.1 . For k = 1 k = 1 k = 1 , target 101 times out (t.o.) and the reported lower bound is 100. The counters #cc and #sc are cumulative counts of lifted rank inequalities (21) and spectral rank inequalities (30) , respectively; the broader counters in Appendix § 10 also include the other tested cut families.
The first target, q = 1 q = 1 q = 1 , includes construction of the auxiliary graph and the shortest-path inequalities. Its recorded time ranges from 102 to 696 seconds. Subsequent targets reuse this preprocessing. In the displayed ranges q = 2 q = 2 q = 2 –53, 2–26, 2–18, and 2–13 for k = 1 , 2 , 3 , 4 k = 1, 2, 3, 4 k = 1 , 2 , 3 , 4 , respectively, each target takes about 0.6 seconds. These timings alone do not identify whether a clique was obtained by an integral LP solution, a primal heuristic, or branching.
For k = 2 k = 2 k = 2 , the successful targets through q = 30 q = 30 q = 30 take approximately 440 seconds in total, while the reported nonexistence conclusion at q = 31 q = 31 q = 31 takes 2937 seconds, about 87% of the total runtime. The cumulative number of spectral rank cuts increases from 72 to 26744 at that target, so 26672 are added during the final search. At the end of that search, the cumulative count exceeds the 3355 lifted rank inequalities shown in the table. These two counters exclude other combinatorial and non-selected-vertex cuts, which are included in Appendix § 10 .
For k = 1 k = 1 k = 1 , target 101 reaches the time limit without finding a clique of that size or excluding it, leaving the reported lower bound 100. This behavior motivates upper bounds that can close the search at a successful target. The recorded spectral bounds for k = 2 , 3 , 4 k = 2,3,4 k = 2 , 3 , 4 are 166, 86, and 32, respectively, so they do not close the runs at the starred values 30, 22, and 16. A valid upper bound of 30 for the k = 2 k = 2 k = 2 case would have removed the final target-31 search. This is a consequence of the stopping rule, not a measured result for an alternative bound.
Effect of the tested configurations
The ablation uses three configurations. Both enables the combinatorial and spectral cuts and the spectral upper bound q max q_{\max} q m a x . Comb. enables only the combinatorial cuts and uses q max = ∣ V ∣ q_{\max} = |V| q m a x = ∣ V ∣ . Spec. enables the spectral cuts and the spectral upper bound, with no combinatorial cuts. All three use the same sequential framework and graph reduction. The counts in Table 5 are obtained from Appendix § 10 ; a success means solver-reported optimality under § 6.1 .
Table 5. Solver-reported successes of the tested configurations. The union counts combinations successful in at least one configuration and does not describe a run with a common total-time budget.
The total number of successes is similar for Both and Comb., while Spec. resolves substantially fewer combinations. Both has three successes that Comb. lacks, and Comb. has two that Both lacks. Spec. supplies one further success absent from Both. These observations support a complementary role for the configurations, while the overall difference between Both and Comb. is modest.
The instance-level times show larger contrasts. For BuckyBall at k = 1 k = 1 k = 1 , Both returns a starred value in 7 seconds whereas Spec. times out. Klein3Regular takes 3 seconds with Both and 5496 seconds with Spec. For Cell120 at k = 2 k = 2 k = 2 , Both returns a starred value of 120 in 645 seconds, whereas Spec. returns the lower bound 81. On 1dc.256 at k = 1 k = 1 k = 1 , Both returns a starred value of 30 in 88 seconds, while Spec. reaches only the lower bound 26 before timeout.
Spectral information can help through either separation or termination at q max q_{\max} q m a x . On Cameron at k = 1 k = 1 k = 1 , the recorded bound q max = 21 q_{\max} = 21 q m a x = 21 matches the returned clique size, allowing Both to finish in 22 seconds; Comb. times out while searching beyond its clique of size 21. For 1et.512 at k = 2 k = 2 k = 2 , the bound 166 is far above the returned value 30, and Both completes target 31 while Comb. times out. Conversely, on 1et.256 at k = 1 k = 1 k = 1 , Comb. returns the starred value 50 in 2060 seconds under the appendix’s rounding convention, whereas Both times out.
Because the tested configurations change both spectral separation and the global bound, they do not isolate the cost or benefit of spectral cuts alone. A controlled comparison would retain the same q max q_{\max} q m a x and preprocessing while switching only spectral separation, and would record separation time by family. The z z z -scaled inequalities and corrected non-selected-vertex cuts also require separate experiments before computational gains can be attributed to those theoretical strengthenings.
Comparison with the discretized formulation of Martins
We compare the recorded results with the discretized formulation (DF) of Martins [22 ] , specifically model (14)–(15) together with constraints (9), (10), (12), and (13) of that paper. DF solves the clique problem on G ‾ \overline{G} G directly, without an outer loop over target sizes. Its implementation uses the same C++ and CPLEX environment, hardware, single-thread setting, and zero requested optimality gap. It receives the degree bound q ≤ Δ ( G ‾ ) + 1 q \le\Delta(\overline{G}) + 1 q ≤ Δ ( G ) + 1 but none of the additional cuts or spectral bounds. Models with more than 2 ⋅ 10 8 2 \cdot10^{8} 2 ⋅ 1 0 8 nonzero coefficients were excluded by the memory threshold and are marked mem.
In addition to the three main classes, this comparison includes 80 DIMACS graphs [17 ] . Each supplied graph is treated as the input G G G to k k k -MIS. Consequently, at k = 1 k = 1 k = 1 the objective is its independence number and the clique solver acts on its complement. These are not timings for the customary maximum-clique objective on the supplied DIMACS graph.
Budgets and aggregation DF has a nominal three-hour limit per instance and k k k , whereas the sequential method has a three-hour limit per target. The recorded comparison includes selected DF runs with extended limits. Across all four classes, the displayed runtime of our method exceeds three hours on 113 combinations; only three of these are starred, all on sum-rank instances whose DF model was excluded. Appendix § 9 contains 38 entries combining a displayed runtime above three hours for our method with a DF timeout. The dagger-marked entry for 1et.256 at k = 1 k = 1 k = 1 displays the successful Comb. runtime instead of the longer unresolved Both runtime. The timing summaries therefore compare the recorded runs and configurations, rather than performance under a single common total-time budget.
The ours column of Table 6 includes the three dagger-marked single-family successes. This aggregation is the union of observed success sets, with the displayed runtime taken from the identified successful run; it excludes the cost of trying the other configurations. For the three main classes, Both alone has 55 successes absent from DF, while the union has 58. The corresponding DF-only count is one. These distinctions are necessary when interpreting the summary as evidence about an individual algorithm or a portfolio.
Table 6. Comparison with the discretized formulation (DF) of Martins [22 ] . For each family and k k k : number of combinations (n n n ); solver-reported successes for the reported results of our configurations (ours) and DF; DF timeouts (t.o.) and models excluded by the nonzero threshold (mem); and overlap of the success sets. The ours column includes the three dagger-marked single-family results; it is not the fixed Both configuration. Mean runtimes use the common success set and a shift of 1 s; the timing summaries retain whole-second rounding for our method. § 6.5 explains the budget and aggregation limitations, and § 6.1 defines solver-reported optimality.
Table 6 retains the reported shifted geometric mean runtime on each common success set. For runtimes t 1 , … , t s t_1,\ldots,t_s t 1 , … , t s measured in seconds, the statistic with a one-second shift is
exp ( 1 s ∑ j = 1 s log ( 1 + t j ) ) − 1. \exp\left(\frac{1}{s}\sum_{j=1}^{s}\log(1+t_j)\right)-1. exp ( s 1 j = 1 ∑ s log ( 1 + t j ) ) − 1.
The times for our method were rounded down to whole seconds in these summaries. Small means and ratios involving them are sensitive to that rounding; the available aggregates do not support precise subsecond speed comparisons. The per-instance values and status counts are given in Appendix § 9 .
Observed outcomes On the named graphs, the reported results include 313 successes for our configurations and 304 for DF. DF has ten timeouts and two excluded models, and no DF-only success. On the coding-theoretic and sum-rank classes, our configurations have 24 and 25 successes absent from DF, respectively. DF has 19 and 27 timeouts in these classes, together with 37 and 33 excluded models. Its sole main-class success absent from our configurations is the 512-vertex sum-rank graph with t = 6 t=6 t = 6 , q = 2 q=2 q = 2 , n = m = ( 2 , 1 5 ) n=m=(2,1^{5}) n = m = ( 2 , 1 5 ) at k = 4 k=4 k = 4 , for which DF returns 4 after 6581 seconds.
On DIMACS at k = 1 k=1 k = 1 , our method has 41 successes and DF has 36, with 33 in common. Eight are exclusive to our method and three—brock200_1, brock200_4, and sanr200_0.7—are exclusive to DF. For k ≥ 2 k\ge2 k ≥ 2 , our method has 80 successes at each value of k k k , and DF has 77; the DF timeouts are c-fat500-1, c-fat500-2, and c-fat500-5. Whenever both methods report optimality, their objective values agree. This consistency is useful evidence about the computations, subject to the numerical-status convention already stated.
Conclusion
We have developed a sequential branch-and-cut framework for maximum k k k -independent sets in which each target clique size gives a compact model with one binary variable per remaining vertex and a continuous activation variable. We have proved the exactness of this model, derived activation-scaled rank inequalities and their liftings, and strengthened the non-selected-vertex inequality. These cuts dominate their unscaled counterparts in the fixed-size relaxation. We use classical spectral bounds both for global stopping and for local rank certificates on complements of subgraphs of the current working graph. Evaluating the bounds on that graph is essential after edge peeling. Under valid bounds, valid cuts, and completed solves, Theorem 5.1 establishes exactness independently of the completeness of the separation heuristics.
The reported implementation gives 470 solver-reported successes among 544 main-benchmark combinations, and the union with the single-family runs gives 473. The ablation identifies instances on which spectral information helps and others on which its additional work is unhelpful. It also shows that spectral separation must be distinguished from the stopping bound. The comparison
with Martins’ discretized formulation yields more reported successes for the sequential configurations on these benchmark classes, while also identifying DF-only successes and limitations caused by differing budgets and configuration aggregation.
Several developments follow directly from the analysis. The continuous-z z z formulation without the redundant rows, z z z -scaled cuts, and corrected non-selected-vertex inequalities should be evaluated against the computational variant studied here. A proof-producing implementation requires certified spectral calculations or independent validation of every affected bound and cut, together with stored clique witnesses. Comparisons using a common total-time budget, identical global bounds where appropriate, unrounded runtimes, and specialised maximum-clique solvers would clarify the computational contribution of each ingredient. Polynomial spectral bounds obtained directly from G G G [3 , 7 , 6 ] , improved primal heuristics, and implicit representations of the auxiliary graph provide further directions for reducing preprocessing and unsuccessful-target costs.
Acknowledgements
Aida Abiad is supported by NWO (Dutch Research Council) through the grants VI.Vidi.213.085 and OCENW.KLEIN.475.
Use of artificial intelligence ChatGPT (OpenAI) was used to assist with mathematical proofreading, exposition, and LaTeX preparation. The authors assume responsibility for all content.
Aida Abiad, Email: a.abiad.monge@tue.nl
Department of Mathematics and Computer Science, Eindhoven University of Technology, The Netherlands
Department of Mathematics and Data Science, Vrije Universiteit Brussel, Belgium
Julian Golak, Email: julian.golak@uni-hamburg.de
University of Hamburg Business School, Institute of Operations Management, Germany
Arne Schulz, Email: arne.schulz@uni-hamburg.de
University of Hamburg Business School, Institute of Operations Management, Germany
Per-instance comparison with the discretized formulation
Table A1 gives the reported values and runtimes of our configurations and the DF formulation under § 6.5 . The starred and dagger-marked entries use the conventions of § 6.1 ; the ours column incorporates the three identified single-family substitutions and is not a fixed-Both comparison. Unstarred entries are reported lower bounds. The table includes the DIMACS results, which are not repeated in the main instance tables. For the sum-rank instances, x j x^{j} x j abbreviates j j j consecutive entries equal to x x x in a parameter tuple.
Table A1: Per-instance comparison with DF [22 ] . For each k k k , columns give the reported value and runtime in seconds, rounded down. An asterisk denotes solver-reported optimality as defined in § 6.1 . For our configurations, † marks a single-family result and its time in place of the unresolved Both run. For DF, t.o. denotes a timeout under the recorded budget and the adjacent value is its incumbent; – denotes a model excluded by the nonzero threshold. Budgets and aggregation are described in § 6.5 .
Table A1.
Table 8.
Table 9.
Table 10.
Ablation tables
Tables B1–B6 report the individual runs underlying § 6.4 . Each group gives the returned value, runtime, and accumulated cut counts for Both and for Comb. or Spec. An asterisk denotes solver-reported optimality under § 6.1 . Each value belongs to the indicated configuration and k k k ; bounds are not transferred across k k k or across configurations. Consequently, a single-family column can contain a larger lower bound than the corresponding main-table entry.
The counter cc includes anticlique, lifted rank, and shortest-path inequalities; sc includes spectral rank and the tested weaker non-selected-vertex inequalities (34) . These are the unscaled inequalities used in the computational variant of § 5 . Counters accumulate over all targets. Runtimes are rounded to the nearest second and may differ by one second from the rounded-down values in the main tables and Appendix § 9 .
Table B1. Named graph instances: both cut families (Both) versus combinatorial cuts only (Comb.). Panel (a): k = 1 , 2 k=1,2 k = 1 , 2 .
Table B1 (PDF p. 43). Named graph instances: both cut families (Both) versus combinatorial cuts only (Comb.). Panel (b): k = 3 , 4 k=3,4 k = 3 , 4 . Continued.
Table B2. Coding-theoretic instances: both cut families (Both) versus combinatorial cuts only (Comb.). Panel (a): k = 1 , 2 k=1, 2 k = 1 , 2 .
Table B2 (PDF p. 46). Coding-theoretic instances: both cut families (Both) versus combinatorial cuts only (Comb.). Panel (b): k = 3 , 4 k=3,4 k = 3 , 4 . Continued.
Table B3. Sum-rank-metric graph instances: both cut families (Both) versus combinatorial cuts only (Comb.). Panel (a): k = 1 , 2 k=1,2 k = 1 , 2 .
Table B3 (PDF p. 48). Sum-rank-metric graph instances: both cut families (Both) versus combinatorial cuts only (Comb.). Panel (b): k = 3 , 4 k=3,4 k = 3 , 4 . Continued.
Table B4: Named graph instances: both cut families (Both) versus spectral cuts only (Spec.). Panel (a): k = 1 , 2 k = 1, 2 k = 1 , 2 .
Table B4. Named graph instances: both cut families (Both) versus spectral cuts only (Spec.). Panel (a): k = 1 , 2 k = 1, 2 k = 1 , 2 .
Table B5. Coding-theoretic instances: both cut families (Both) versus spectral cuts only (Spec.). Panel (a): k = 1 , 2 k = 1, 2 k = 1 , 2 .
Table B5 (PDF p. 54). Coding-theoretic instances: both cut families (Both) versus spectral cuts only (Spec.). Panel (b): k = 3 k=3 k = 3 , 4 4 4 . Continued.
Table B6. Sum-rank-metric graph instances: both cut families (Both) versus spectral cuts only (Spec.). Panel (a): k = 1 , 2 k=1,2 k = 1 , 2 .
Table B6 (PDF p. 56). Sum-rank-metric graph instances: both cut families (Both) versus spectral cuts only (Spec.). Panel (b): k = 3 , 4 k=3,4 k = 3 , 4 . Continued.