Fixed-Parameter Algorithms for Graph-Modeled Data Clustering - Clustering Challenges in Biological Network - page 22

cessful, running times increased sharply. Additional experiments for the feature
model mentioned at the beginning of this section showed that random instances
with 100 items and up to 30 features could be solved within a few minutes.
Two reduction rules of Gramm et al. (Rule CC3 and another rule that we do
not discuss here) have so far not been proved to improve the size of the problem
kernel and are also quite slow to compute. For some instances, however, both rules
were beneficial, meaning that the obtained speedups for them instances were much
larger than observed slowdowns for other instances. This suggests the general
application of these rules, possibly with an additional heuristic to disable them
based on instance properties.
As a final note, unlike the C LUSTER E DITING model, C LIQUE C OVER does
not take perturbed data into account. In practice, probably edges within feature
clusters are missing, and spurious edges exist. However, this can be handled with
a post-processing: as long as there are not too many errors, spurious edges will
be covered by size-2 cliques, which can be easily filtered; and a clique missing
an edge will be optimally covered by two cliques, and so in a post-processing one
can check for all pairs of cliques whether they could be merged by adding a small
number of edges.
1.4. Conclusion
We conclude our survey with a list of guidelines for the practical design of fixed-
parameter algorithms and some open challenges in the field.
1.4.1. Practical Guidelines
The following list sums up the experiences of our and other research groups who
have implemented fixed-parameter algorithms:
Fixed-Parameter Tractability in General
(1) Do not despair of bad upper bounds for fixed-parameter algorithms that
are given in theoretically oriented papers—the analysis is worst-case and
often much too pessimistic.
(2) Fixed-parameter algorithms are the better the smaller the parameter value
is. Hence, parameterizations with small parameter values should be
sought after.
(3) Most existing fixed-parameter algorithms in the literature are concerned
with optimization problems on unweighted graphs. Solving enumerative