betaFeedback

WorksMathematics

Branch-and-Cut for Maximum kk-Independent Sets with Spectral Bounds

Abstract

We develop a branch-and-cut method for finding maximum distance-independent sets in graphs. Our approach solves a sequence of fixed-size clique problems, combining graph reductions with combinatorial and spectral bounds. We give a compact formulation, derive strengthened inequalities, establish conditions for using spectral information, and evaluate them in a comprehensive computational study.

Introduction

Let GG be a simple undirected graph and let kk be a positive integer. A set of vertices is kk-independent if the distance between any two distinct vertices in the set exceeds kk. Its maximum possible cardinality is the kk-independence number, denoted by αk(G)\alpha_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 kk-independent set is NP-hard for every fixed positive kk [18, 19, 5, 12]. The problem can be expressed as an independent set problem in the graph power GkG^k, which joins vertices whose distance in GG is at most kk, 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 kk-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 unless stated otherwise; for the graph with no vertices, αk(G)=0\alpha_k(G) = 0. The distance dist⁡G(i,j)\operatorname{dist}_G(i,j) is the number of edges on a shortest path from ii to jj, and is infinite when the vertices lie in different connected components. When such a path exists, SPG(i,j)SP_G(i,j) denotes one shortest path, viewed as an ordered vertex sequence. For a graph H=(U,F)H = (U,F), write H[W]H[W] for the subgraph induced by W⊆UW \subseteq U, H‾\overline{H} for its complement, NH(i)N_H(i) for the open neighborhood of ii, and dH(i)=∣NH(i)∣d_H(i) = |N_H(i)| for its degree. We write y(W)=∑i∈Wyiy(W) = \sum_{i \in W} y_i and use ω(H)\omega(H) and α1(H)\alpha_1(H) for the clique and independence numbers. The notation G‾=Gk\overline{G} = G^k is reserved for the original auxiliary graph; HH denotes a current working graph and Hq=(Vq,Eq)H_q = (V_q,E_q) the graph after reductions for target size qq.

For a graph HH, let ω(H)\omega(H) denote its clique number, with ω(∅)=0\omega(\varnothing)=0. Given an instance G=(V,E)G=(V,E) of kk-MIS, define the auxiliary graph

G‾=(V,E‾),E‾={{i,j}∈(V2):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\}.

Thus G‾=Gk\overline{G}=G^{k}, and the definitions give

αk(G)=α1(Gk)=ω(G‾).(1)\alpha_{k}(G)=\alpha_{1}(G^{k})=\omega(\overline{G}). \tag*{(1)}

Indeed, a set of vertices has pairwise distance greater than kk in GG if and only if all its pairs are edges of G‾\overline{G} [3, 2]. The auxiliary graph can be constructed in polynomial time by computing shortest-path distances [20]; vertices in different connected components of GG are adjacent in G‾\overline{G}. The empty input graph has αk(G)=0\alpha_{k}(G)=0 and is handled directly. For the remainder of this section, assume V≠∅V\ne\varnothing.

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|\} contain ω(G‾)\omega(\overline{G}). The binary variable wqw_q selects size qq, and xiqx_{iq} indicates whether vertex ii belongs to the clique selected at that size. The formulation is

max⁡∑i∈V∑q∈Qxiq(2)\max\sum_{i\in V}\sum_{q\in Q}x_{iq} \tag*{(2)}
s.t.∑q∈Qwq=1,(3)\text{s.t.}\qquad\sum_{q\in Q}w_q=1, \tag*{(3)}
∑j∈NG‾(i)xjq≥(q−1)xiq∀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)}
∑i∈Vxiq=qwq∀q∈Q,(5)\sum_{i\in V}x_{iq}=qw_q\qquad\forall q\in Q, \tag*{(5)}
wq∈{0,1}∀q∈Q,(6)w_q\in\{0,1\}\qquad\forall q\in Q, \tag*{(6)}
xiq∈{0,1}∀i∈V, q∈Q(7)x_{iq}\in\{0,1\}\qquad\forall i\in V,\ q\in Q \tag*{(7)}

Exactly one size is active. At that size, every selected vertex has the other q−1q-1 selected vertices as neighbors, so the selected set is a clique. The assumption on QQ therefore makes the optimal objective value equal to ω(G‾)\omega(\overline{G}). The number of variables grows with ∣Q∣|Q|, which motivates solving one size at a time.

Let H=(U,F)H=(U,F) be the working auxiliary graph: initially H=G‾H=\overline{G}, and after preprocessing it is the reduced graph defined in § 2.3. We write NH(i)N_H(i) and dH(i)d_H(i) for its neighborhoods and degrees. For a fixed integer q≥1q\ge1, consider

max⁡∑i∈Uyi(8)\max\sum_{i\in U}y_i \tag*{(8)}
s.t.∑j∈NH(i)yj≥(q−1)yi∀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)}
∑i∈Uyi=qz,(10)\sum_{i\in U} y_i = qz, \tag*{(10)}
yi∈{0,1}∀i∈U,(11)y_i \in\{0,1\}\qquad\forall i\in U, \tag*{(11)}
z∈[0,1].(12)z \in[0,1]. \tag*{(12)}

Here yy selects the vertices, while zz permits either a qq-clique or the empty solution. The variable zz is continuous.

Proposition 2.1 (Exactness of the fixed-size formulation). For every finite simple graph HH and every integer q≥1q \ge1, the feasible solutions of (8)–(12) are precisely (y,z)=(0,0)(y,z)=(0,0) and (y,z)=(1C,1)(y,z)=(\mathbf{1}_C,1), where CC is a clique of size qq in HH. Consequently, its optimal objective value is qq if such a clique exists and 00 otherwise.

Proof. Let (y,z)(y,z) be feasible and set C={i∈U:yi=1}C=\{i\in U:y_i=1\}. If C=∅C=\varnothing, then (10) and q≥1q\ge1 give z=0z=0. Otherwise, choose i∈Ci\in C. Constraint (9) gives at least q−1q-1 selected neighbors of ii, and hence ∣C∣≥q|C|\ge q. On the other hand, (10) and z≤1z\le1 give ∣C∣≤q|C|\le q. Thus ∣C∣=q|C|=q and z=1z=1. Applying (9) to each i∈Ci\in C shows that ii is adjacent to every vertex of C∖{i}C\setminus\{i\}, so CC is a clique. Conversely, the empty solution and the incidence vector of any qq-clique satisfy every constraint. The argument also covers q=1q=1 and U=∅U=\varnothing.

The formulation has ∣U∣|U| binary variables, one continuous variable, and ∣U∣+1|U|+1 linear constraints apart from variable bounds, with O(∣U∣+∣F∣)O(|U|+|F|) nonzero coefficients. Eliminating zz gives the equivalent formulation obtained by replacing (10) and (12) with ∑i∈Uyi≤q\sum_{i\in U} y_i\le q. We retain zz because it provides a useful strengthening of the cuts in § 3. The LP relaxation also implies

0≤yi≤z(i∈U):(13)0 \le y_i \le z \qquad(i\in U): \tag*{(13)}

indeed, (9) and (10) give (q−1)yi≤∑j∈NH(i)yj≤qz−yi(q-1)y_i\le\sum_{j\in N_H(i)}y_j\le qz-y_i.

Relation to the experimental implementation

The implementation used in § 6 declares zz binary and retains the additional rows

∑j∈NH(i)yj≤q−yi(i∈U).(14)\sum_{j\in N_H(i)} y_j \le q-y_i \qquad(i\in U). \tag*{(14)}

Proposition 2.1 shows that the integrality restriction on zz does not change the integer feasible solutions. Moreover, (14) is redundant even in the LP relaxation, since

∑j∈NH(i)yj≤∑j∈U∖{i}yj=qz−yi≤q−yi.\sum_{j\in N_H(i)} y_j \le\sum_{j\in U\setminus\{i\}} y_j = qz-y_i \le 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≥2q \ge2, two deletion rules reduce the auxiliary graph before the fixed-size problem is solved: a vertex ii may be deleted when dH(i)<q−1d_H(i) < q - 1, and an edge {i,j}\{i,j\} may be deleted when ∣NH(i)∩NH(j)∣<q−2\lvert N_H(i) \cap N_H(j)\rvert< 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=1q = 1 needs no reduction: a nonempty graph contains a one-vertex clique.

References

  1. [1]Aida Abiad, Sebastian M. Cioabă, and Michael Tait. Spectral bounds for the k-independence number of a graph. Linear Algebra Appl., 510:160–170, 2016. 2, 11arxiv.org/abs/1510.07186
  2. [2]Aida Abiad, Gabriel Coutinho, and Miguel Angel Fiol. On the k-independence number of graphs. Discrete Math., 342(10):2875–2885, 2019. 1, 2, 3, 11
  3. [3]Aida Abiad, Gabriel Coutinho, Miguel Angel Fiol, Bruno D. Nogueira, and Sianne Zeijlemaker. Optimization of eigenvalue bounds for the independence and chromatic number of graph powers. Discrete Math., 345(3):112706, 2022. https://doi.org/10.1016/j.disc.2021.112706. 1, 2, 3, 11, 19, 29
  4. [4]Aida Abiad, Antonina P. Khramova, and Alberto Ravagnani. Eigenvalue bounds for sum-rank-metric codes. IEEE Trans. Inf. Theory, 70(7):4843–4855, 2024. https://doi.org/10.1109/TIT.2023.3339808. 1, 2, 11, 18, 19, 23
  5. [5]Aida Abiad and Hidde Koerts. On the complexity of the k-independence number and the h-diameter of a graph. Mat. Contemp., 55:30–38, 2023. 1DOI
  6. [6]Aida Abiad, Stan van Hoesel, and Valentin Michaux. Optimization and complexity of inertia-type bounds on the independence and chromatic numbers of graph powers. arXiv:2605.00524, 2026. 2, 29arxiv.org/abs/2605.00524
  7. [7]Aida Abiad and Jiang Zhou. Algebraic bounds for the independence and chromatic number of graph powers. SIAM J. Matrix Anal. Appl., 47(2):467–482, 2026. https://doi.org/10.1137/25M1746057. 2, 29
  8. [8]Immanuel M. Bomze, Marco Budinich, Panos M. Pardalos, and Marcello Pelillo. The maximum clique problem. In Ding-Zhu Du and Panos M. Pardalos, editors, Handbook of Combinatorial Optimization: Supplement Volume A, pages 1–74. Kluwer Academic Publishers, Boston, MA, 1999. https://doi.org/10.1007/978-1-4757-3023-4_1. 1
  9. [9]Vašek Chvátal. On certain polytopes associated with graphs. J. Combin. Theory Ser. B, 18(2):138–154, 1975. https://doi.org/10.1016/0095-8956(75)90041-6. 2, 7, 12
  10. [10]Jonathan Cohen. Trusses: Cohesive subgraphs for social network analysis. Technical report, National Security Agency, 2008. 5
  11. [11]Dragoš M. Cvetković. Graphs and their spectra. Publikacije Elektrotehničkog fakulteta. Serija Matematika i fizika, (354/356):1–50, 1971. 10
  12. [12]Hiroshi Eto, Fengrui Guo, and Eiji Miyano. Distance-d independent set problems for bipartite and chordal graphs. J. Comb. Optim., 27(1):88–99, 2014. https://doi.org/10.1007/s10878-012-9594-4. 1
  13. [13]Chris Godsil and Michael W. Newman. Eigenvalue bounds for independent sets. J. Combin. Theory Ser. B, 98(4):721–734, 2008. https://doi.org/10.1016/j.jctb.2007.10.007. 11
  14. [14]Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 1988. https://doi.org/10.1007/978-3-642-97881-4. 7
  15. [15]Willem H. Haemers. Interlacing eigenvalues and graphs. Linear Algebra Appl., 226–228:593–616, 1995. https://doi.org/10.1016/0024-3795(95)00199-2. 10
  16. [16]Jochen Harant and Sebastian Richter. A new eigenvalue bound for independent sets. Discrete Math., 338(10):1763–1765, 2015. https://doi.org/10.1016/j.disc.2014.12.008. 11
  17. [17]David S. Johnson and Michael A. Trick, editors. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, volume 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1996. 26
  18. [18]M. C. Kong and Yijun Zhao. On computing maximum k-independent sets. Congr. Numer., 95:47–60, 1993. 1
  19. [19]M. C. Kong and Yijun Zhao. Computing k-independent sets for regular bipartite graphs. Congr. Numer., 143:65–80, 2000. 1
  20. [20]Bernhard Korte and Jens Vygen. Combinatorial Optimization: Theory and Algorithms. Springer, 4th edition, 2008. https://doi.org/10.1007/978-3-540-71844-4. 3
  21. [21]László Lovász. On the Shannon capacity of a graph. IEEE Trans. Inf. Theory, 25(1):1–7, 1979. 13DOI
  22. [22]Pedro Martins. Extended and discretized formulations for the maximum clique problem. Comput. Oper. Res., 37(7):1348–1358, 2010. https://doi.org/10.1016/j.cor.2009.10.010. 1, 3, 5, 17, 26, 28, 34
  23. [23]George L. Nemhauser and Leslie E. Trotter. Properties of vertex packing and independence system polyhedra. Math. Program., 6(1):48–61, 1974. https://doi.org/10.1007/BF01580222. 2
  24. [24]Manfred W. Padberg. On the facial structure of set packing polyhedra. Math. Program., 5(1):199–215, 1973. https://doi.org/10.1007/BF01580121. 7
  25. [25]Steffen Rebennack, Marcus Oswald, Dirk Oliver Theis, Hanna Seitz, Gerhard Reinelt, and Panos M. Pardalos. A branch and cut solver for the maximum stable set problem. J. Comb. Optim., 21(4):434–457, 2011. https://doi.org/10.1007/s10878-009-9264-3. 2, 7, 12
  26. [26]Fabrizio Rossi and Stefano Smriglio. A branch-and-cut algorithm for the maximum cardinality stable set problem. Oper. Res. Lett., 28(2):63–74, 2001. https://doi.org/10.1016/S0167-6377(00)00060-2. 2, 7, 12
  27. [27]Neil J. A. Sloane. Challenge problems: Independent sets in graphs. OEIS Foundation, 2017. https://oeis.org/A265032/a265032.html. 17
  28. [28]The Sage Developers. SageMath, the Sage Mathematics Software System, 2024. https://www.sagemath.org. 17
  29. [29]Alexander Veremyev, Vladimir Boginski, Eduardo L. Pasiliao, and Oleg A. Prokopyev. Ultra-small world detection in networks: subgraphs with prescribed distance distributions. Computational Optimization and Applications, 92:1069–1121, 2025. https://doi.org/10.1007/s10589-024-00640-1. 2
  30. [30]Anurag Verma, Austin Buchanan, and Sergiy Butenko. Solving the maximum clique and vertex coloring problems on very large sparse networks. INFORMS J. Comput., 27(1):164–177, 2015. https://doi.org/10.1287/ijoc.2014.0618. 5
  31. [31]Qinghua Wu and Jin-Kao Hao. A review on algorithms for maximum clique problems. Eur. J. Oper. Res., 242(3):693–709, 2015. https://doi.org/10.1016/j.ejor.2014.09.064. 1, 7

Paper details

vlnc:W_wxw4a475
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT (OpenAI)

View statement
Looking for related papers…
Contents