Vertex Separator Problem (VSP) - Instances and results (Updated 13 May 2014)

This page shows the best results obtained by Breakout Local Search (BLS) for VSP:

Una Benlic and Jin-Kao Hao. Breakout Local Search for the Vertex Separator Problem. Proc. of the 23th Intl. Joint Conference on Artificial Intelligence (IJCAI-13), pages 461-467, August 2013, Beijing, China.

The source code is here (Please make sure that the above paper is cited if you use the code in your research).  The software is distributed for academic puposes only. If you wish to use this software for commercial applications, please obtain a permission from Una Benlic (benlic@info.univ-angers.fr) or Jin-Kao Hao (hao@info.univ-angers.fr).

Problem definition

Given a connected undirected graph G = (V, E), a cost ci associated to each vertex i ∈ V, and an integer 1 ≤ b ≤ |V|, the vertex separator problem (VSP) is to find a partition of V into disjoint subsets A, B, C with A and B non-empty, such that (i) there is no edge (i, j) ∈ E such that i ∈ A, j ∈ B , (ii) max{|A|, |B|} ∈ b and (iii) ∑{cj : j ∈ C} is minimized. A and B are called shores of the separator C. A separator C is a legal (feasible) solution if it satisfies the problem constraints (i) and (ii), and is termed optimal if (i), (ii) and (iii) are met.

Instance files

This VSP benchmark consists of a set of 54 toroidal, planar and random graph, generated by Helmberg and Rendl [Helmberg and Rendl, 2000]. The number of vertices ranges from |V| = 800 to 3000. All the vertices are given unit weights and b = ⌊1.05|V|/2⌋. The format of these data files is:


b value, number of nodes (n), number of edges

for each node i (i = 1,...,n) in turn:
'v', node, node cost

for each edge (i,j) (i,j=1,...,n, i < j) in turn:
'e', i, j, edge cost

Output format

The output format is a string of size |V|, such that the ith element corresponds to the subset of vertex i. The value 0 indicates that a vertex is in the separator, while values 1 and 2 indicate that the vertex is in shores A and B respectively.

Table1. Best results obtained by Breakout Local Search (BLS) algorithm.
Instance Best res. Instance Best res.
G1 257 G28 822
G2 257 G29 820
G3 257 G30 821
G4 363 G31 819
G5 257 G32 40
G6 257 G33 50
G7 257 G34 80
G8 257 G35 435
G9 257 G36 440
G10 257 G37 434
G11 16 G38 439
G12 32 G39 435
G13 45 G40 440
G14 146 G41 435
G15 144 G42 439
G16 144 G43 411
G17 144 G44 411
G18 146 G45 410
G19 144 G46 412
G20 144 G47 411
G21 144 G48 100
G22 588 G49 60
G23 590 G50 50
G24 589 G51 224
G25 589 G52 223
G26 587 G53 221
G27 820 G54 219