Information Technology Reference
In-Depth Information
edges.
G
k
is a minor of
G
and, for
i<k
,
G
i
is a minor of a graph obtained from
G
i
+1
by contracting an edge incident to
s
i
.
For
i
=2
,...,k
:
-
G
i
[
S
i
] is a maximal simple subgraph of
G
i
+1
[
S
i
]; therefore tw(
G
i
+1
[
S
i
]) =
max
by Fact 2.
-
G
i
[
S
i
] is obtained from
G
i
[
S
i−
1
] by the subdivision of an edge (by
s
i
)orthe
addition of a leaf vertex (
s
i
); therefore tw(
G
i
[
S
i
]) = max
{
1
,
tw (
G
i
[
S
i
])
}
{
1
,
tw (
G
i
[
S
i−
1
])
}
by
Facts 1 and 3.
By induction and the fact that a graph with a single vertex has treewidth 0, the
lemma follows.
m
Lemma 2.
5
.
Proof.
We show, equivalently, that the procedure deletes at most
5
vertices by
amortized analysis. For each vertex that we delete we incur a charge of
|
S
|≥
n
−
5. For
each edge that we contract (incident to a degree-1 or -2 vertex), remove (as a
self-loop or parallel edge) or delete (by way of deleting an adjacent vertex) we
incur a charge of +1. Note that we distinguish between deleting and removing
an edge for the purpose of this analysis. We will show that the net charge is
positive, thus showing that for every 5 edges of the graph, we delete at most one
vertex.
The first case of the algorithm, in which an edge is contracted, incurs only
a positive charge. There are three remaining cases in which a vertex is deleted,
according to the degree of the deleted vertex and whether it is adjacent to a
degree 3 vertex.
Deleting a degree-3 vertex from a 3-regular graph.
Deleting such a vertex
incurs a charge of +3
−
−
−
2 but creates three degree-2 vertices. At least one
edge incident to each of these will be contracted (or removed) for a total charge
of +3. Therefore, before another vertex is deleted, the net charge for deleting
this vertex is at least +1.
Deleting a degree-4 vertex adjacent to a degree-3 vertex.
Deleting such
avertex
v
incurs a charge of +4
5=
1 but creates at least one vertex
u
of degree 2; an edge incident to
u
will be contracted before another vertex is
deleted. The net charge for deleting
v
is at least 0.
Deleting a degree-4 vertex from a 4-regular graph.
Deleting such a vertex
incurs a charge of +4
−
5=
−
1. After this case happens, the remaining graph will
have at least four degree-3 vertices, and will continue to have a nonzero number
of both degree-3 and degree-4 vertices until either the graph becomes 4-regular
again (by reducing the degree-3 vertices to degree-2 and contracting them away)
or all degree-4 vertices have been removed. We consider the following sub-cases
for the steps of the algorithm that either return to a 4-regular state or eliminate
all degree-4 vertices:
−
5=
−
(a) If the graph becomes 4-regular again, it can only be after removing a degree-
4 vertex adjacent to four degree-3 vertices, followed by four contractions of
