Information Technology Reference
In-Depth Information
2 Preliminaries
Bridges vs Flaps and Isthmuses.
There is an unfortunate terminological confu-
sion in graph theory: two different concepts, a maximal subgraph that is inter-
nally connected by paths that avoid a given cycle, and an edge whose removal
disconnects the graph, are both commonly called
bridges
. We need both concepts
in our algorithms. To avoid confusion, we call the subgraph-type bridges
flaps
and the edge-type bridges
isthmuses
. To be more precise, given a graph
G
and
acycle
C
, we define an equivalence relation on the edges of
G
C
in which two
edges are equivalent if they belong to a path that has no interior vertices in
C
,
and we define a
flap
of
C
to be the subgraph formed by an equivalence class of
this relation. (Different cycles may give rise to different flaps.) Given a graph
G
,
we define an
isthmus
of
G
to be an edge of
G
that does not belong to any simple
cycles in
G
.
\
Treewidth and Graph Minors.
The
treewidth
of
G
can be defined to be one less
than the number of vertices in the largest clique in a chordal supergraph of
G
that
(among possible chordal supergraphs) is chosen to minimize this clique size [6].
The problem of computing the treewidth of a general graph is
NP
-hard [1], but
it is fixed-parameter tractable in its natural parameter [5].
Agraph
H
is said to be a
minor
of a graph
G
if
H
can be constructed from
G
via a sequence edge contractions, edge deletions, and vertex deletions. It can
be determined whether a graph
H
is a minor of a graph
G
, in time that is
polynomial in the size of
G
and fixed-parameter tractable in the size of
H
[21].
Logic of Graphs.
We will be expressing graph properties in
extended monadic
second-order logic
(MSO
2
). This is a fragment of second-order logic that includes:
-
variables for vertices, sets of vertices, edges, and sets of edges;
-
binary relations for equality (=), inclusion of an element in a set (
∈
)and
edge-vertex incidence (I);
-
the standard propositional logic operations:
¬
,
∧
,
∨
,
ₒ
;
-
the universal quantifier (
∀
) and the existential quantifier (
∃
), both which
may be applied to variables of any of the four variable types.
To distinguish the variables of different types, we will use
u,v,w,...
for vertices,
e,f,g,...
for edges, and capital letters for sets of vertices or edges (with context
making clear which type of set). Given a graph
G
and an MSO
2
formula
ˆ
we
write
G
=
ˆ
(“
G
models
ˆ
”) to express the statement that
ˆ
is true for the
vertices, edges, and sets of vertices and edges in
G
, with the semantics of this
relation defined in the obvious way. MSO
2
differs from full second order logic in
that it allows quantification over sets, but not over higher order relations, such
as sets of pairs of vertices that are not subsets of the given edges.
The reason we care about expressing graph properties in MSO
2
is the following
powerful algorithmic meta-theorem due to Courcelle.
|
