A √n-Approximation for Independent Sets: The Furones Algorithm

The Maximum Independent Set (MIS) problem, a core NP-hard problem in graph theory, seeks the largest subset of vertices in an undirected graph G = (V, E) with n vertices and m edges, such that no two vertices are adjacent. We present a hybrid approximation algorithm that combines iterative refinement with greedy selections based on minimum and maximum degrees, plus a low-degree induced subgraph heuristic, implemented using NetworkX. The algorithm preprocesses the graph to handle trivial cases and isolates, computes exact solutions for bipartite graphs using Hopcroft-Karp matching and K\"onig's theorem, and, for non-bipartite graphs, iteratively refines a candidate set via maximum spanning trees and their maximum independent sets, followed by a greedy extension. It also constructs independent sets by selecting vertices in increasing and decreasing degree orders, and computes an independent set on the induced subgraph of low-degree vertices (degree strictly less than maximum), returning the largest of the four sets. An efficient O (m) independence check ensures correctness. The algorithm guarantees a valid, maximal independent set with a worst-case n-approximation ratio, tight for graphs with a large clique connected to a small independent set, and robust for structures like multiple cliques sharing a universal vertex. With a time complexity of O (n m n), it is suitable for small-to-medium graphs, particularly sparse ones. While outperformed by O (n / n) -ratio algorithms for large instances, it aligns with inapproximability results, as MIS cannot be approximated better than O (n^1-) unless P = NP. Its simplicity, correctness, and robustness make it ideal for applications like scheduling and network design, and an effective educational tool for studying trade-offs in combinatorial optimization, with potential for enhancement via parallelization or heuristics.