# 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.