论文 ID ATH-2L6WCC
· 一区论文
· 分子与细胞生物学
Targeted Branching for the Maximum Independent Set Problem Using Graph Neural Networks CC-BY
这是一篇从 DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) 导入的开放获取论文,用于长期保存;它并非本站投稿,因此不设版本历史与时间戳历史。
- 原出版日期:2024年1月1日 UTC
- 权利状态:CC-BY(未记录届满日期)
- 加入本站:2026年10月3日 UTC
由以下人员代作者上传 AthenXiv (UW2JTS24Y)
摘要
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 components that can impact the efficiency of these algorithms have not received the same level of interest. Among these is the branching strategy, which determines which vertex to branch on next. Until recently, the most widely used strategy was to choose the vertex of the highest degree. In this work, we present a graph neural network approach for selecting the next branching vertex. The intricate nature of current branch-and-bound solvers makes supervised and reinforcement learning difficult. Therefore, we use a population-based genetic algorithm to evolve the model’s parameters instead. Our proposed approach results in a speedup on 73% of the benchmark instances with a median speedup of 24%.
关键词: Bioinformatics and Genomic Networks, Molecular Biology, Biochemistry, Genetics and Molecular Biology, Life Sciences
DOI: 10.4230/lipics.sea.2024.20
许可协议: CC-BY
在线阅读
外部链接
- DOI DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.20
引用本文
Silva, Gabriel, Rodrigues, Mário, Teixeira, António, Amorim, Marlene (2026).
Targeted Branching for the Maximum Independent Set Problem Using Graph Neural Networks. AthenXiv.
https://athenxiv.com/paper/ATH-2L6WCC