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 c_i 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 i^th 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