Casting light on the hidden bilevel combinatorial structure of the k-Vertex Separator problem
Abstract: Given an undirected graph, a k-vertex separator is a vertex subset the removing of which disconnects the graph in k shores (subsets of vertices), pair-wise disconnected. We study the capacitated k-Vertex Separator problem (k-VSP) which asks to find a k-vertex separator of minimum cardinality such that the size of each shore is not bigger than a given capacity value u. The problem is of great importance for matrix decomposition algorithms and in the analysis and protection of communication or social networks against possible viral attacks. In this article we provide a fresh and new bilevel interpretation of the problem, and model it as a two-player Stackelberg game, in which the leader interdicts the vertices (i.e., decides on the separator), and the follower solves a combinatorial problem on the resulting graph. This approach allows us to develop a computational framework based on an Integer Programming formulation in the natural space of the variables. Thanks to this bilevel interpretation, we derive three different families of strengthening inequalities and show that they can be separated in polynomial time. Our extensive computational study conducted on available benchmark instances from the literature reveals that our new exact method is competitive against the state-of-the-art algorithms for the k-VSP, and is able to improve the best known results for several difficult classes of instances.
Keywords: Bilevel Optimization; Stackelberg Games; Graph decomposition; Branch-and-Cut; Benders decomposition.
Category 1: Combinatorial Optimization
Category 2: Combinatorial Optimization (Branch and Cut Algorithms )
Category 3: Network Optimization
Citation: OR-19-6, DEI, University of Bologna, 2019
Entry Submitted: 09/27/2019
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|