Nam Le

Maximum Independent Set

Nam Le
Table of Contents

Maximum Independent Set #

The Maximum Independent Set problem is about finding the largest subset of vertices in a graph with no edges between them. It’s an NP-hard problem with important applications.

Recent Literature #

  1. Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search. NeurIPS, 2018. paper

    Li, Zhuwen and Chen, Qifeng and Koltun, Vladlen.

  2. Learning What to Defer for Maximum Independent Sets ICML, 2020. paper

    Ahn, Sungsoo and Seo, Younggyo and Shin, Jinwoo

  3. Distributed Scheduling Using Graph Neural Networks ICASSP, 2021. paper

    Zhao, Zhongyuan and Verma, Gunjan and Rao, Chirag and Swami, Ananthram and Segarra, Santiago

  4. Solving Graph-based Public Good Games with Tree Search and Imitation Learning NeurIPS, 2021. paper

    Darvariu, Victor-Alexandru and Hailes, Stephen and Musolesi, Mirco

  5. NN-Baker: A Neural-network Infused Algorithmic Framework for Optimization Problems on Geometric Intersection Graphs NeurIPS, 2021. paper

    McCarty, Evan and Zhao, Qi and Sidiropoulos, Anastasios and Wang, Yusu

  6. What’s Wrong with Deep Learning in Tree Search for Combinatorial Optimization ICLR, 2022. paper, code

    Bother, Maximilian and Kissig, Otto and Taraz, Martin and Cohen, Sarel and Seidel, Karen and Friedrich, Tobias

  7. Optimistic tree search strategies for black-box combinatorial optimization NeurIPS, 2022. paper

    Malherbe, Cedric and Grosnit, Antoine and Tutunov, Rasul and Ammar, Haitham Bou and Wang, Jun

  8. ⭐ROCO: A General Framework for Evaluating Robustness of Combinatorial Optimization Solvers on Graphs ICLR, 2023. paper, code

    Lu, Han and Li, Zenan and Wang, Runzhong and Ren, Qibing and Li, Xijun and Yuan, Mingxuan and Zeng, Jia and Yang, Xiaokang and Yan, Junchi

  9. Revisiting Sampling for Combinatorial Optimization ICML, 2023. paper

    Sun, Haoran, Goshvadi Katayoon,Nova Azade,Schuurmans Dale and Dai Hanjun.

  10. DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization NeurIPS, 2023. paper, code

    Zhiqing Sun, Yiming Yang

  11. ⭐T2T: From Distribution Learning in Training to Gradient Search in Testing for Combinatorial Optimization NeurIPS, 2023. paper, code

    Yang Li, Jinpei Guo, Runzhong Wang, Junchi Yan

  12. Unsupervised Learning for Combinatorial Optimization Needs Meta Learning ICLR, 2023. paper, code

    Wang, Haoyu and Li, Pan

  13. Graph-based Deterministic Policy Gradient for Repetitive Combinatorial Optimization Problems ICLR, 2023. paper, code

    Zhao, Zhongyuan and Swami, Ananthram and Segarra, Santiago

  14. Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets NeurIPS, 2023. paper, code

    Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron Courville, Yoshua Bengio, Ling Pan

  15. Variational Annealing on Graphs for Combinatorial Optimization NeurIPS, 2023. paper, code

    Sanokowski, Sebastian and Berghammer, Wilhelm Franz and Hochreiter, Sepp and Lehner, Sebastian

  16. Maximum Independent Set: Self-Training through Dynamic Programming NeurIPS, 2023. paper, code

    Brusca, Lorenzo and Quaedvlieg, Lars CPM and Skoulakis, Stratis and Chrysos, Grigorios G and Cevher, Volkan

  17. DISCS: A Benchmark for Discrete Sampling NeurIPS, 2023. paper, code

    Katayoon Goshvadi, Haoran Sun, Xingchao Liu, Azade Nova, Ruqi Zhang, Will Sussman Grathwohl, Dale Schuurmans, Hanjun Dai

  18. MARCO: A Memory-Augmented Reinforcement Framework for Combinatorial Optimization IJCAI, 2024. paper, code

    Andoni I. Garmendia, Quentin Cappart, Josu Ceberio, Alexander Mendiburu

  19. ⭐Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization NeurIPS, 2024. paper, code

    Yang Li, Jinpei Guo, Runzhong Wang, Hongyuan Zha, Junchi Yan

  20. Controlling Continuous Relaxation for Combinatorial Optimization NeurIPS, 2024. paper

    Yuma Ichikawa

  21. Distributed Constrained Combinatorial Optimization leveraging Hypergraph Neural Networks Nature Machine Intelligence, 2024. paper, code

    Nasimeh Heydaribeni, Xinrui Zhan, Ruisi Zhang, Tina Eliassi-Rad, Farinaz Koushanfar

  22. Efficient Combinatorial Optimization via Heat Diffusion NeurIPS, 2024. paper

    Hengyuan Ma, Wenlian Lu, Jianfeng Feng

  23. A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization ICML, 2024. paper, code

    Sanokowski, Sebastian and Hochreiter, Sepp and Lehner, Sebastian

  24. Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics ICLR, 2025. paper

    Sebastian Sanokowski, Wilhelm Franz Berghammer, Haoyu Peter Wang, Martin Ennemoser, Sepp Hochreiter, Sebastian Lehner

  25. ⭐COExpander: Adaptive Solution Expansion for Combinatorial Optimization ICML, 2025. paper, code

    Jiale Ma and Wenzheng Pan and Yang Li and Junchi Yan

  26. ⭐ML4CO-Bench-101: Benchmark Machine Learning for Classic Combinatorial Problems on Graphs NeurIPS, 2025. paper, code

    Jiale Ma and Wenzheng Pan and Yang Li and Junchi Yan

Tags:
Categories: