Game Development Reference

In-Depth Information

consists of showing that whenever there is a search tree of width
k
in a graph

G
then there is a monotone search tree of the same width.

Sub-modularity

We begin by introducing the concept of sub-modularity and an extension

thereof.

Definition 7.19

Let
E
beasetand
φ
: Pow(
E
)

→
N

be a function.

1
φ
is
symmetric
if
φ
(
X
)=
φ
(
E \ X
) for all
X ⊆ E
.

2
φ
is
sub-modular
if
φ
(
X
)+
φ
(
Y
)

≥

φ
(
X

∩

Y
)+
φ
(
X

∪

Y
) for all
X, Y

⊆

E
.

A symmetric and sub-modular function is called a
connectivity function
.

For our proof here we will work with an extension of sub-modularity to

partitions of a set
E
.

Definition 7.20

If
P
:=

{

X
1
,...,X
k
}∈P

(
E
) is a partition of a set
E

and
F

E
then we define
P
X
i
↑F
as

P
X
i
↑F
:=

⊆

F
c
,X
i
+1
∩

{

X
1
∩

F, ..., X
i−
1
∩

F, X
i
∪

F,...,X
k
∩

F

}

,

where
F
c
:=
E

\

F
.

Definition 7.21

Let
E
beaset.A
partition function
is a function

φ
:

P

(
E
)

→
N

.
φ
is
sub-modular
if for all
P
:=

{

X
1
,...,X
k
}∈P

(
E
)
,Q
:=

{

Y
1
,...,Y
s
}∈P

(
E
) and all
i, j

φ
(
P
)+
φ
(
Q
)

≥

φ
(
P
X
i
↑Y
j
)+
φ
(
Q
Y
j
↑X
i
)
.

It is worth pointing out that the definition of sub-modularity of partition

functions indeed extends the usual definition of sub-modularity as defined

above. For, if
P
:=

X, X
c

Y, Y
c

{

}

and
Q
:=

{

}

are bipartitions of a set
E

then

φ
(
P
)+
φ
(
Q
)
≥ φ
(
P
X↑Y
c
)+
φ
(
Q
Y
c
↑X
)

=
φ
(
X ∪
(
Y
c
)
c
,X
c

∩ Y
c
)+
φ
(
Y ∩ X, Y
c

∪ X
c
)

=
φ
(
X ∪ Y, X
c

∪ X
c
)

=
φ
(
X ∪ Y,
(
X ∪ Y
)
c
)+
φ
(
Y ∩ X,
(
Y ∩ X
)
c
)
.

∩ Y
c
)+
φ
(
Y ∩ X, Y
c

Hence, if we set Φ(
X
):=
φ
(
X, X
c
) then this corresponds to the usual notion

of sub-modularity of Φ as defined above.

We show next that the border function in Definition 7.16 is sub-modular.

Lemma 7.22
Let G be a graph and φ
(
P
):=
|δ
(
P
)
| for all partitions

P ∈P
(
E
(
G
))
. Then φ is sub-modular.

Search Nedrilad ::

Custom Search