Thursday 27
Graphs, flows, combinatorial algorithms and approximation
Vincent Chau
› 11:00 - 11:30 (30min)
› Bât B - TD 43
A semidefiinite programming relaxation for Vertex Separator Problem
Chuan Xu  1, *@  , Abdel Lisser  1, *@  , Rendl Frenz  2  
1 : Laboratoire de Recherche en Informatique  (LRI)  -  Website
Université de Paris-Sud Orsay
2 : Universität Klangenfurt  -  Website
Universitätsstrae 65-67 Klangenfurt -  Autriche
* : Corresponding author

Vertex Separator Problem (VSP for short) is a well known NP complete graph problem. VSP consists in separating the graph into k parts of the same size. In this talk, we firstly propose an integer programming formulation for VSP in the case where k=2, and use the commercial solver CPLEX to obtain optimal solutions for small instances, i.e., graph with less than 125 nodes. Then, we introduce an efficient semidefinite programming relaxation (SDP for short). We solve the SDP relaxation by using the bundle method. We also propose an efficient variant of variable neighborhood search (VNS for short) to obtain feasible solutions. We combine both SDP and VNS to come up with good feasible solutions. Our numerical results show that our SDP model provides a good starting point for VNS which leads to results comparable with the best literature ones for graphs with up to 2000 nodes.


Online user: 1