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

Targeted Branching for the Maximum Independent Set Problem Using Graph Neural Networks 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 branc...