Game Development Reference
In-Depth Information
Lemma 7.40 If G has a tree-decomposition of width k then it also has a
tree-decomposition of width k in normal form.
Proof
Let
T
:= ( T, ( B t ) t∈V ( T ) ) be a tree-decomposition of G . Let t
V ( T ).
By Lemma 7.38, for every component C of G
\
B t there is exactly one
neighbour s of t such that V ( C )
B ( T s ), where T s is the component of
t containing s . So suppose that there are two components C, C such that
T
C
T be the tree-decomposition
C
B ( T s ) for some neighbour s of t . Let
obtained from
as follows. Take an isomorphic copy of T s rooted at a vertex
s and add this as an additional neighbour of t . In the next step we replace
every B ( l )by B ( l )
T
V ( T s ). We
proceed in this way till we reach a tree-decomposition in normal form of the
same width.
V ( C )if l
V ( T s ) and by B ( l )
\
V ( C )if l
The presence of a tree-decomposition of small width in a graph G is a
witness that the graph has a rather simple structure and that its tree-width
is small. But what would a certificate for large tree-width look like? If the
tree-width of a graph is very large than there should be some structure in it
that causes this high tree-width. Such structural reasons for width parameters
to be high are usually referred to as obstructions . It turns out that using a
graph searching game connection of tree-width, such obstructions can easily
be identified as we can use the formalisations of winning strategies for the
robber given in Section 7.5 above.
We aim next at establishing a game characterisation of tree-width in terms
of the visible Cops and Robber game. It is not di cult to see that strategy
trees for monotone winning strategies correspond to tree-decompositions.
Lemma 7.41 Let G be an undirected graph of tree-width at most k +1 .
Then k cops have a monotone winning strategy on G in the visible cops and
robber game. Conversely, if k +1 cops have a monotone winning strategy in
the visible cops and robber game on G then the tree-width of G is at most k.
Proof Assume first that k + 1 cops have a monotone winning strategy
on G and let
:= ( T,cops, robber ) be a strategy tree witnessing this as
defined in Definition 7.14. As
T
represents a monotone strategy, we can
w.l.o.g. assume that for each node t
T
V ( T ), cops ( t ) only contains vertices
that can be reached by the robber. Formally, if t
V ( T ) and t 1 ,...,t r are its
out-neighbours, then if v
cops ( t ) there must exist an edge
{
v, u
}∈
E ( G )
with u
robber (( t, t i )) for at least one i . Clearly, it is never necessary to put
a cop on a vertex that has no neighbour in the robber space as these cops
cannot be reached by the robber. It is a simple exercise to show that under
this assumption ( T, ( cops ( t )) t∈V ( T ) ) is a tree-decomposition of G .