Information Technology Reference
In-Depth Information
list of configurations for each case can all be done in constant time per case,
leading to a linear overall time bound.
Theorem 1 is tight: there exist arbitrarily large graphs in which the largest
induced pseudoforest has exactly
n
m/
4
.
5 vertices. In particular, let
G
be a
graph formed by the disjoint union of
n/
6 copies of the complete bipartite graph
K
3
,
3
. Then, to form a pseudoforest in
G
, we must delete at least two vertices
from each copy of
K
3
,
3
, for deleting only one vertex leaves
K
2
,
3
which is not a
pseudoforest. Each copy has nine edges, so the number of deleted vertices must
be at least
m/
4
.
5. The same class of examples shows that even if we are searching
for the broader class of induced outerplanar subgraphs, we may need to delete
m/
4
.
5 vertices.
−
4 Large Induced Treewidth Two Graphs
In this section, we prove Theorem 2 by showing that we can delete at most
m
5
vertices from a graph
G
with
m
edges to leave a graph with treewidth at
most 2. By Observation 1, we may assume without loss of generality
G
has
degree at most 4. We prove the theorem algorithmically by arguing that the
following procedure builds a vertex set
S
of size at least
n
m
5
such that
G
[
S
]
has treewidth at most 2. The procedure modifies the graph by edge contractions
but does not increase its degree over 4.
−
S
=
∅
make
G
simple by removing self-loops and parallel edges
while
G
has more than 1 vertex:
if there is a vertex
v
of degree one or two:
contract an edge incident to
v
and add
v
to
S
:
make
G
simple by removing self-loops and parallel edges
else if
G
contains a vertex of degree three:
delete a vertex of the largest degree adjacent to a degree-three vertex
else:
delete a vertex of maximum degree
add the last remaining vertex to
S
Lemma 1.
The induced subgraph G
[
S
]
produced by the algorithm above has
treewidth at most 2.
Proof.
We use the following facts:
Fact 1. If
H
is a subdivision of
G
then tw(
G
)=max
.
Fact 2. If
H
is a maximal simple subgraph of
G
then tw(
G
)=max
{
1
,
tw (
H
)
}
{
1
,
tw (
H
)
}
.
Fact 3. If
H
is obtained from
G
by deleting a leaf vertex, tw(
G
)=max
{
1
,
tw (
H
)
}
.
Let
s
1
,s
2
,...,s
k
be the vertices of
S
in the reverse of the order in which they
were added to
S
.Let
S
i
=
.Let
G
i
be the graph at
the start of the iteration in which vertex
s
i
is added to
S
;let
G
k
+1
=
G
.
G
i
is a minor of
G
, obtained by deletions of vertices and edge and contractions of
{
s
1
,s
2
,...,s
i
}
;let
S
0
=
∅
