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
.

∈

Search Nedrilad ::

Custom Search