Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem
将通信或社交网络中限制病毒传播的顶点保护问题建模为Stackelberg博弈，通过双层优化推导出可多项式时间分离的加强不等式，对图分割和顶点删除问题有推广价值。
Exploiting Bilevel Optimization Techniques to Disconnect Graphs into Small Components In order to limit the spread of possible viral attacks in a communication or social network, it is necessary to identify critical nodes, the protection of which disconnects the remaining unprotected graph into a bounded number of shores (subsets of vertices) of limited cardinality. In the article “'Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem”, Furini, Ljubic, Malaguti, and Paronuzzi provide a new bilevel interpretation of the associated capacitated vertex separator problem and model it as a two-player Stackelberg game in which the leader interdicts (protects) the vertices, and the follower solves a combinatorial optimization problem on the resulting graph. Thanks to this bilevel interpretation, the authors derive different families of strengthening inequalities and show that they can be separated in polynomial time. The ideas exploited in their framework can also be extended to other vertex/edge deletion/insertion problems or graph partitioning problems by modeling them as two-player Stackelberg games to be solved through bilevel optimization.