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.