Biology Reference
In-Depth Information
Fig. 1.1.
A graph with a size-8 vertex cover (cover vertices are marked black, the solution size is
optimal).
1.2. Fixed-Parameter Tractability Basics and Techniques
In this section, we introduce the basics of fixed-parameter tractability, in particular
exhibiting two techniques that are of major practical importance
a
and have by now
facilitated many success stories in bioinformatics, namely
•
kernelizations, that is, data reductions with provable performance guar-
antees (Sec. 1.2.1) and
•
depth-bounded search trees (Sec. 1.2.2).
Both techniques are introduced by means of a single natural and easy to grasp
problem, namely the NP-hard V
ERTEX
C
OVER
problem.
V
ERTEX
C
OVER
I
NPUT
: An undirected graph
G
=(
V,E
) and a nonnegative
integer
k
.
T
ASK
: Find a subset of vertices
C
V
with
k
or fewer vertices
such that each edge in
E
has at least one of its endpoints in
C
.
⊆
This problem is illustrated in Fig. 1.1 and is—among many other applications—of
central importance to practically solving the C
LIQUE
problem that we discuss in
Sec. 1.3.1.
b
Throughout this work, we assume basic knowledge from algorithmics [19, 48]
and graph theory [24, 71]. For a given undirected graph
G
=(
V,E
),wealways
use
n
to denote the number of its vertices and
m
to denote the number of its edges.
For
v
∈
V
,weuse
N
G
(
v
) to denote the neighbor set
{
v
∈
V
|{
u,v
}∈
E
}
and
N
G
[
v
] to denote the closed neighborhood
N
G
(
v
)
∪{
v
}
, omitting the indices
whenever they are clear from the context.
The core approach of fixed-parameter tractability [25, 30, 60] is to consider
parameterized problems
—that is, problems that consist of the instance
I
and a pa-
a
A broader view on fixed-parameter algorithm design techniques can be found in Ref. 60.
b
V
ERTEX
C
OVER
is the
Drosophila
of fixed-parameter research in that many initial discoveries that
influenced the whole field originated from studies of this single problem (e.g., see Guo et al. [40]).
Search WWH ::
Custom Search