Targeted Branching for the Maximum Independent Set Problem Using Graph Neural Networks

Silva, Gabriel, Rodrigues, Mário, Teixeira, António et al.

2024 · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 5,381 citations

Identifying a maximum independent set is a fundamental NP-hard problem. This problem has several real-world applications and requires finding the largest possible set of vertices not adjacent to each other in an undirected graph. Over the past few years, branch-and-bound and branch-and-reduce algorithms have emerged as some of the most effective methods for solving the problem exactly. Specifically, the branch-and-reduce approach, which combines branch-and-bound principles with reduction rules, has proven particularly successful in tackling previously unmanageable real-world instances. This p…

Read the paper →

Explore this paper's citation graph on Constellation.