🚀 go-pugleaf

Hi,

I have a problem (and want it solved ;-)):

Does anyone know the relationship between the two versions of 
graph separators ?

Keywords: separator, vertex separator, pathwidth, node search number

Thomas Lengauer described in his article "Black-White Pebbles and 
Graph Separation" (Acta Informatica 16, 465-475 (1981))
the well-known "static" version of graph separators and he introduced
a "dynamic" version.

Can anyone give me a hint to the relation between the "dynamic" and the
"static" separator ?

The static version:

An undirected graph G=(V,E) with n vertices has a f(n) separator iff
V can be separated in three disjunct sets A, B and S, A and B have 
no edges in common, (1/3)n <= #A <= (2/3)n, (1/3)n <= #B <= (2/3). 
S contains no more than f(n) vertices. A and B have also a 
f(n) separator (recursively applied on A and B).


The dynamic version: 

I give here T. Lengauer's definition:
"... The above definition of a separator is a 'static' one. We will here
define a corresponding(*) 'dynamic' notion of a separator. The definition
will be in terms of a pebble game on undirected graphs called the Vertex
Separator Game (VSG).
The VSG is played on undirected graphs G according to the following rules.

(i)   All vertices start out pebble-free.
(ii)  All vertices end up pebbled.
(iii) A move consists of placing a pebble on a pebble-free vertex.

The Vertex Cut after the i-th move consists of all vertices that are pebble-
free and adjacent to a pebbled vertex after the i-th move. Let S be a
strategy for VSG on G [G is the graph], i.e. a permutation of the vertices 
of G that represents a sequence of moves (applications of rule (iii)) in
VSG. ..."
(*) Well, that's my problem "corresponding".

And the vertex cut of a strategy is the maximum vertex cut after every move.
The dynamic or vertex separator is the minumum vertex cut of all strategies
for the graph.
Related graph theoretic topics are the node search number and pathwidth
of an undirected graph. 
That is  node search number -1 = pathwidth = dynamic separator.

Is it possible to transform a "static" to a "dynamic" separator and 
vice versa ?

Please send any ideas or hints to my address. Thanks ! 
Email-address: schweika@trillian.fmi.uni-passau.de

Thank you
                Andreas Schweikardt
-- 
Andreas Schweikardt * Ingling 17 * 4784 Schardenberg * Austria
                    trillian@fmi.uni-passau.de