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 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 progress was largely made possible by the development of more effective reduction rules. Nevertheless, other key…

• EC
  European Commission

  Award: 882500
• RC
  Royal College of Nursing, Australia
• NF
  Norges Forskningsråd
• FP
  Fundação para a Ciência e a Tecnologia

  Award: UIDB/00127/2020