A Novel Hybrid Approach for Independence Number Estimation Using Spectral Lower Bound for Independent Sets and Adaptive Greedy Algorithm
Karrar Khudhair Obayes *
Department of Computer Information Systems, University of Al-Qadisiyah, Al Diwaniyah, Iraq.
*Author to whom correspondence should be addressed.
Abstract
The independent number of a graph, which represents the set of non-contiguous vertices, is a cornerstone of graph theory with applications spanning network security, circuit design, and social community detection. However, calculating the independence number is extremely difficult, and this is a challenge for large graphs. Traditional methods such as exact algorithms (e.g., Brun-Kerbosch) suffer from exponential complexity, while these methods often trade precision for speed. In this paper, we present a new hybrid framework that combines the Spectral Lower Bound for Independent Sets limit and adaptive greedy inference. The methodology is demonstrated in three stages: Spectral analysis ensures the computation of the maximum eigenvalue (λ max) of the adjacency matrix to generate the Spectral Lower Bound for Independent Sets. Greedy expansion: prioritises nodes with low degrees and dynamically prunes their neighbours to maximise the independent set. Hybrid verification: determines the maximum score from both stages. A comparative study with Branch-and-Bound and MCS algorithms shows a speedup of 30-40% for graphs with n ≤ 1000 vertices without compromising accuracy.
Keywords: Independence number, spectral lower bound, independent sets, hybrid framework