An Approximate Independent Set Solver: 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 a vertex-cover complement approach 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 via Hopcroft-Karp matching and K”{o}nig’s theorem, and, for non-bipartite graphs, iteratively processes connected components by computing $2$-approximate minimum vertex covers whose complements serve as independent set candidates, refined by a gadget-graph technique and extended greedily to maximality. It also constructs independent sets by selecting vertices in increasing and decreasing degree orders and by restricting to a low-degree induced subgraph, returning the largest of the four candidates. An efficient $O(m)$ independence check ensures correctness. The algorithm provably achieves a $2$-approximation ratio for bipartite graphs (optimal) and for graphs where $mathrm{OPT} geq 2n/3$ (via a tight vertex-cover complement bound), and attains a maximum observed ratio of $1.833$ across all $37$ DIMACS benchmark instances, well within the $2$-approximation guarantee. Its time complexity is $O(nm)$, making it suitable for small-to-medium graphs. Its simplicity, correctness, and robustness make it ideal for scheduling, network design, and combinatorial optimization education, with potential for enhancement via parallelization.