Scalable maximum independent set computation for conflict graphs using kernelization and greedy inference

Recent branch-based MaxIS solvers improve solution quality through recursive search and targeted branching [Hespe D, Lamm S, Schorr C. Targeted branching for the maximum independent set problem. 2021], but their runtime can grow rapidly on large IoT conflict graphs. This paper proposes KernelGreedyMaxIS, a deterministic polynomial-time framework for scalable independent-set computation. The method combines lightweight degree-based kernelization with minimum-degree greedy inference, separating locally justified reductions from heuristic selection. This design improves reproducibility, avoids random seeds and training data, and provides predictable runtime behavior. Theoretical analysis proves reduction correctness, feasibility, deterministic termination, and O(n2logn) worst-case complexity. Experiments show competitive solution quality with fast runtime on benchmark and real-world graphs.