Information Technology Reference
In-Depth Information
Observation 1.
If every graph of maximum degree at most
k
−
contains an
1
induced subgraph with property
P
and at least n
−
m/k vertices, then the same
is true for every graph.
Proof.
We use induction on
n
.Let
G
contain a vertex
v
of degree
k
, and let
G
be formed from
G
by removing
v
. By the induction hypothesis,
G
has an
induced subgraph
H
with the desired property
≥
m
(
G
)
k
P
and at least
n
(
G
)
−
vertices. Then
H
is an induced
P
-subgraph of
G
with size at least
m
(
G
)
k
m
(
G
)
− k
k
m
(
G
)
k
n
(
G
)
−
1
−
≥
n
(
G
)
−
1
−
=
n
(
G
)
−
.
3 Large Induced Pseudoforests
In this section, we prove Theorem 1 by showing that we can delete at most
4
.
5
vertices from a graph
G
with
m
edges to leave a pseudoforest; by Observation 1,
we assume
G
hasdegreeatmost4.
We repeatedly perform the first applicable reduction in the following list of
cases, until no edges are left. As we do, we construct a set
S
of vertices that
will induce our desired subgraph. Initially
S
is empty and when no edges are
left we add all remaining vertices to
S
. The steps of the reduction essentially
identify “dangling trees” and contract these. After a series of vertex deletions
(which identify vertices that will not belong the final induced subgraph) and
edge contractions, if we create a component that consists of a single cycle (in
fact a triangle, case
Δ
-a and
Vertex of degree 4
(c) (i) and (ii)), we “keep” this
component; this triangle is the minor of an induced cycle in our final induced
subgraph which will only be incident to the “dangling trees” which had been
contracted into the cycle. This guarantees that the final induced subgraph has
at most one cycle per component. To bound the size of the output
S
in terms of
the number of edges, we use an amortized analysis, incurring a charge of
4
.
5for
every deleted vertex and a charge of +1 for every removed or contracted edge;
we show that the net charge for every processing step is non-negative. Our cases
are:
Leaf vertex.
If there is a vertex
a
of degree 1, we add
a
to
S
and contract the
edge incident to
a
. This incurs a charge of +1.
Vertex of degree 2 not in a triangle.
If there is a vertex
a
of degree 2 that
is not part of a triangle, we add
a
to
S
and contract an edge incident to
a
.This
incurs a charge of +1.
Vertex of degree 2 in a triangle.
If there is a vertex
a
of degree 2 in a
triangle
abc
then we consider the four sub-cases illustrated below:
−
a
c
(
Δ
-a) If the triangle is isolated: add
a
,
b
and
c
to
S
,andremove
the edges of the triangle from the graph. This incurs a
charge of +3.
b
