Biology Reference
In-Depth Information
k
k
−
1
k
−
1
k −
2
k −
2
k −
2
k
−
2
...
...
...
...
Fig. 1.2. Simple search tree for finding a vertex cover of size at most
k
in a given graph. The size of
the tree is upper-bounded by
O
(2
k
).
one of these two vertices
must
be part of a solution. Thus, a simple search-tree
algorithm to solve V
ERTEX
C
OVER
on a graph
G
proceeds by picking an arbitrary
edge
e
=
{
v,w
}
and recursively searching for a vertex cover of size
k
−
1 both
w
.
e
That is, the algorithm
branches
into two subcases knowing
one of them must lead to a solution of size at most
k
—if one such solution exists.
As shown in Fig. 1.2, these recursive calls of the simple V
ERTEX
C
OVER
algorithm can be visualized as a tree structure. Because the depth of the recursion
is upper-bounded by the parameter value and we always branch into two subcases,
the size of this tree is upper-bounded by
O
(2
k
). This means that the size of the
tree is
independent of the size of the initial input instance
and only depends on the
value of the parameter
k
.
The main idea behind fixed-parameter algorithmics is to get the combinatorial
explosion as small as possible. For our V
ERTEX
C
OVER
example, one can easily
achieve a size-
o
(2
k
) search tree by distinguishing more detailed branching cases
rather than just picking single endpoints of edges to be in the cover.
f
An exam-
ple for such an “improved” search-tree is given in our case study of C
LUSTER
E
DITING
in Sec. 1.3.2. The currently “best” search trees for V
ERTEX
C
OVER
are of size
O
(1
.
28
k
) [15] and mainly achieved by extensive case distinguishing.
However, it should be noted for practical applications that it is always concrete im-
plementation and testing that has to decide whether the administrative overhead
in
G
−
v
and
G
−
e
For a vertex
v
v
to be the graph
G
with
v
and the edges incident to
v
removed.
f
Note that analogously to the case of data reduction, most of these branchings assume that only
one
minimum solution is sought after. Since some graphs can have 2
k
minimum vertex covers, a size-
o
(2
k
) search tree for enumerating
all
minimum vertex covers requires the use of
compact solution
representations
as outlined by Damaschke [21] and is beyond the scope of this work.
∈
V
,wedefine
G
−
Search WWH ::
Custom Search