{"id":"arxiv/2609.25149","url":"https://arxiv.org/abs/2609.25149","tags":["cs.LG","math.CO"],"score":0,"title":"Dual-GNN Multilevel Coarsening for Maximum Independent Set","domain":"cs.LG","source":"arxiv","authors":["Tianfeng Chen","Xianyue Li"],"reviews":0,"subject":"cs.LG","summary":"The maximum independent set (MIS) problem is a fundamental NP-hard combinatorial optimization problem with applications in scheduling, resource allocation, and network analysis. Exact solvers can provide high-quality solutions or optimality certificates, but their computational cost grows rapidly with graph size, while hand-crafted heuristics improve scalability at the expense of guarantees. Learning-based methods offer an alternative by exploiting structural patterns across graph instances, yet directly predicting independent sets can make global coordination difficult on large graphs. We…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-21","reactions":{}}