2011

Conference articles 

2010

Conference articles 

Nadja Betzler,
Jiong Guo,
Christian Komusiewicz, and
Rolf Niedermeier:
Average Parameterization and Partial Kernelization for Computing Medians.
In Proceedings of the 9th Latin American Theoretical Informatics Symposium
(LATIN'10), Oaxaca, México, April 2010.
Volume 6034 in Lecture Notes in Computer Science, pages 60–71, Springer
(original publication).
 René van Bevern,
Christian Komusiewicz,
Hannes Moser, and
Rolf
Niedermeier:
Measuring Indifference:
Unit Interval Vertex Deletion.
In Proceedings of the 36th International Workshop on Graph Theoretic
Concepts in Computer Science
(WG'10),
Zarós (Crete), Greece, June 2010. Volume 6410 in Lecture Notes in Computer
Science, pages 232–243, Springer.

Jiong Guo,
Sepp Hartung,
Christian Komusiewicz,
Rolf Niedermeier, and
Johannes Uhlmann:
Exact Algorithms and Experiments for Hierarchical Tree Clustering.
In Proceedings of the 24th AAAI Conference on Artificial Intelligence
(AAAI'10), Atlanta, GA, USA, July 2010.

Journal articles 

Falk Hüffner,
Christian Komusiewicz,
Hannes Moser, and
Rolf Niedermeier:
Fixedparameter algorithms for cluster vertex deletion.
Theory of Computing Systems 47(1):196–217,
2010
(original publication).
[show abstract]
Abstract.
We initiate the first systematic study of the NPhard Cluster Vertex Deletion (CVD) problem (unweighted and
weighted) in terms of fixedparameter algorithmics. In the unweighted
case, one searches for a minimum number of vertex deletions to transform a
graph into a collection of disjoint cliques. The parameter is the number
of vertex deletions. We present efficient fixedparameter algorithms for
CVD applying the fairly new iterative compression technique. Moreover, we
study the variant of CVD where the maximum number of cliques to be
generated is prespecified. Here, we exploit connections to fixedparameter
algorithms for (weighted) Vertex Cover.

Journal articles (to appear) 

Nadja Betzler,
Jiong Guo,
Christian Komusiewicz, and
Rolf Niedermeier:
Average Parameterization and Partial Kernelization for Computing Medians.
Journal of Computer and System Sciences.
Accepted for publication, July 2010 (original publication).

Nadja Betzler,
René van Bevern,
Michael R. Fellows,
Christian Komusiewicz, and
Rolf Niedermeier:
Parameterized Algorithmics for Finding Connected Motifs in Biological Networks.
IEEE/ACM Transactions on Computational Biology and Bioinformatics.
Accepted for publication, September 2010.

Michael R. Fellows,
Jiong Guo,
Christian Komusiewicz,
Rolf Niedermeier, and
Johannes Uhlmann:
Graphbased data clustering with overlaps.
Discrete Optimization.
Accepted for publication, September 2010 (original publication).

Jiong Guo,
Christian Komusiewicz,
Rolf Niedermeier, and
Johannes Uhlmann:
A more relaxed model for graphbased data clustering: splex cluster editing.
SIAM Journal on Discrete Mathematics.
Accepted for publication, July 2010.

Christian Komusiewicz,
Rolf Niedermeier, and
Johannes Uhlmann:
Deconstructing
Intractability – A Multivariate Complexity Analysis of
Interval Constrained Coloring.
Journal of Discrete Algorithms.
Accepted for publication, July 2010 (original publication).

2009

Conference articles 

Daniel Brügmann, Christian Komusiewicz, and
Hannes Moser:
On Generating TriangleFree Graphs.
In Proceedings of the DIMAP Workshop on Algorithmic Graph Theory
(AGT'09),
Warwick, England, March 2009.
Electronic Notes in Discrete Mathematics 32, pages 51–58, Elsevier
(original publication).
[show abstract]
Abstract.
We show that the problem to decide whether a graph
can be made trianglefree with at most k edge
deletions remains NPcomplete even when restricted
to planar graphs of maximum degree seven. In
addition, we provide polynomialtime data reduction
rules for this problem and obtain problem kernels
consisting of 6k vertices for general graphs and
11k/3 vertices for planar graphs.

Michael R. Fellows,
Jiong Guo,
Christian Komusiewicz,
Rolf Niedermeier, and
Johannes Uhlmann:
GraphBased Data Clustering with Overlaps.
In Proceedings of the 15th International Computing and Combinatorics Conference
(COCOON'09),
Niagara Falls, USA, June 2009.
Volume 5609 in Lecture Notes in Computer Science, pages 516–526, Springer.
[show abstract]
Abstract.
We introduce overlap cluster graph modification problems where, other than in most
previous work, the clusters of the target graph may overlap.
More precisely, the studied graph problems ask for a minimum
number of edge modifications such that the resulting graph
consists of clusters (maximal cliques) that may overlap up to
a certain amount specified by the overlap number s. In the case of
svertex overlap, each vertex may be part of at most s maximal cliques;
sedge overlap is analogously defined in terms of edges.
We provide a complete complexity dichotomy (polynomialtime solvable vs NPcomplete)
for the underlying edge modification problems, develop forbidden subgraph
characterizations of ``cluster graphs with overlaps'', and study
the parameterized complexity in terms of the number of allowed edge
modifications, achieving fixedparameter tractability results
(in case of constant svalues) and parameterized hardness (in case of
unbounded svalues).

Jiong Guo,
Iyad A. Kanj,
Christian Komusiewicz, and
Johannes Uhlmann:
Editing Graphs into Disjoint Unions of Dense Clusters.
In Proceedings of the 20th International Symposium on Algorithms and Computation
(ISAAC'09),
Hawaii, USA, December 2009.
[show abstract]
Abstract.
In the ΠCluster Editing problem, one is given an undirected graph G, a density measure Π,
and an integer k >= 0, and needs to decide whether it is possible to transform G by editing
(deleting and inserting) at most k edges into a dense cluster graph. Herein, a dense cluster graph is
a graph in which every connected component K=(V_{K},E_{K}) satisfies Π. The wellstudied Cluster Editing problem is a special case of this problem
with Π:=“being a clique”. In this work, we consider three other density measures that generalize cliques: 1) having at most s missing edges (sdefective cliques),
2) having average degree at least V_{K}s (averagesplexes), and 3) having average degree at least μ · (V_{K}1) (μcliques), where s and μ
are a fixed integer and a fixed rational number, respectively. We first show that the ΠCluster Editing problem
is NPcomplete for all three density measures. Then, we study the fixedparameter tractability of the three clustering problems, showing that the first two problems are fixedparameter tractable with respect to the parameter (s,k) and that the third problem is W[1]hard with respect to the parameter k for 0<μ<1.

Jiong Guo,
Christian Komusiewicz,
Rolf Niedermeier, and
Johannes Uhlmann:
A More Relaxed Model for GraphBased Data Clustering: sPlex Editing.
In Proceedings of the 5th International Conference on
Algorithmic Aspects in Information and Management
(AAIM'09),
San Francisco, USA, June 2009.
Volume 5564 in Lecture Notes in Computer Science, pages 226–239, Springer.
[show abstract]
Abstract.
We introduce the sPlex Editing problem
generalizing the wellstudied Cluster Editing
problem, both being NPhard and both being motivated by graphbased data clustering.
Instead of transforming a given graph by a minimum number of edge
modifications into a disjoint union of cliques
(Cluster Editing), the task in the case of sPlex Editing
is now to transform a graph into a disjoint union of socalled
splexes. Herein, an splex denotes a vertex set inducing a (sub)graph
where every vertex has edges to all but at most s vertices
in the splex.
Cliques are 1plexes. The advantage of splexes for s≥2
is that they allow to model a more relaxed cluster notion (splexes
instead of cliques),
which better reflects inaccuracies of the input data.
We develop a provably efficient and effective preprocessing based on data reduction
(yielding a socalled problem kernel), a forbidden subgraph
characterization of splex cluster graphs, and a depthbounded
search tree which is used to find optimal edge modification sets.
Altogether, this yields efficient
algorithms in case of moderate numbers of edge
modifications.

Christian Komusiewicz, Rolf Niedermeier, and
Johannes Uhlmann:
Deconstructing Intractability – A Case Study for Interval Constrained Coloring.
In Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching
(CPM'09), Lille, France, June 2009.
Volume 5577 in Lecture Notes in Computer Science, pages 207–220, Springer.
[show abstract]
Abstract.
The NPhard Interval Constrained Coloring problem appears
in the interpretation of experimental data in biochemistry
dealing with protein fragments.
Given a set
of m integer intervals in the range 1 to n and a set
of m associated multisets of colors (specifying for each interval
the colors to be used for its elements), one asks whether there is
a ``consistent'' coloring for all integer points from
{ 1,..., n } that complies with the constraints
specified by the color multisets.
We initiate a study of Interval Constrained Coloring from the
viewpoint of combinatorial algorithmics,
trying to avoid polyhedral and randomized rounding methods as used in
previous work.
To this end, we employ the method of systematically
deconstructing intractability. It is
based on a
thorough analysis of the known NPhardness proof for
Interval Constrained Coloring. In particular, we identify numerous
parameters that naturally occur in the problem and
strongly influence the problem's practical solvability.
Thus, we present several positive (fixedparameter) tractability
results
and, moreover,
identify a large spectrum of combinatorial research challenges
for Interval Constrained Coloring.

Mathias Weller,
Christian Komusiewicz,
Rolf Niedermeier, and
Johannes Uhlmann:
On Making Directed Graphs Transitive.
In Proceedings of the 11th Algorithms and Data Structures Symposium
(WADS'09),
Banff, Canada, August 2009.
Volume 5664 in Lecture Notes in Computer Science, pages 542–553. Springer (original publication).
[show abstract]
Abstract.
We present the first thorough theoretical analysis of the
Transitivity Editing problem on digraphs. Herein,
the task is to perform a minimum number of arc insertions or deletions
in order to make a given digraph transitive.
This problem has recently been identified as important for the detection
of hierarchical structure in molecular characteristics of disease.
Mixing up Transitivity Editing with the companion problems on undirected graphs, it has
been erroneously claimed to be NPhard. We correct this error by
presenting a first proof of NPhardness, which also extends to the restricted cases where the input digraph is acyclic or
has maximum degree four.
Moreover, we improve previous fixedparameter algorithms, now
achieving a running time of O(2.57 ^{k} + n^{3}) for an nvertex digraph
if k arc modifications are sufficient to make it transitive. In particular,
providing an O(k^{2})vertex problem kernel, we positively answer an open
question from the literature. In case of digraphs with
maximum degree d, an O(k· d)vertex problem kernel
can be shown. We also demonstrate that if the input digraph contains no
``diamond structure'', then one can always find an optimal solution that
exclusively performs arc deletions.
Most of our results (including NPhardness)
can be transferred to the Transitivity Deletion problem,
where only arc deletions are allowed.

Journal articles 

Falk Hüffner,
Christian Komusiewicz,
Hannes Moser, and
Rolf Niedermeier:
Isolation concepts for clique enumeration: comparison and computational experiments.
Theoretical Computer Science, 410(52):5384–5397, 2009
(original publication).
[show abstract]
Abstract.
We do computational studies concerning the enumeration of
isolated cliques in graphs. Isolation, as recently introduced,
measures the degree of connectedness of the cliques to the rest
of the graph. Isolation helps both in getting faster algorithms
than for the enumeration of maximal general cliques and in
filtering out cliques with special semantics. We compare three
isolation concepts and their combination with two enumeration
modi for maximal cliques (“isolated maximal” vs
“maximal isolated”). All studied concepts exhibit
the fixedparameter tractability of the enumeration task with
respect to the parameter “degree of isolation”. We
provide a first systematic experimental study of the
corresponding enumeration algorithms, using synthetic graphs (in
the G_{n,m,p} model),
financial networks, and a music artist similarity network
(proposing the enumeration of isolated cliques as a useful
instrument in analyzing financial and social networks).

Christian Komusiewicz,
Falk Hüffner,
Hannes Moser, and
Rolf Niedermeier:
Isolation concepts for efficiently enumerating dense subgraphs.
Theoretical Computer Science, 410(38–40):3640–3654, 2009
(original publication).
[show abstract]
Abstract.
In an undirected graph G = (V, E), a set
of k vertices is called cisolated if it has less
than c · k outgoing edges. Ito and Iwama [ACM
Trans. Algorithms, to appear] gave an algorithm to enumerate all
cisolated maximal cliques in
O(4^{c} · c^{4} ·
E) time. We extend this to enumerating all maximal
cisolated cliques (which are a superset) and improve the
running time bound to O(2.89^{c} · c² ·
E), using modifications which also facilitate
parallelizing the enumeration. Moreover, we introduce a more
restricted and a more general isolation concept and show that
both lead to faster enumeration algorithms. Finally, we extend
our considerations to splexes (a relaxation of the
clique notion), providing a W[1]hardness result when the size
of the splex is the parameter and a fixedparameter
algorithm for enumerating isolated splexes when the
parameter describes the degree of isolation.

2008

Conference articles 

Nadja Betzler,
Michael R. Fellows,
Christian Komusiewicz, and
Rolf Niedermeier:
Parameterized algorithms and hardness results for some graph motif problems.
In Proceedings of the 19th Annual Symposium on Combinatorial Pattern Matching
(CPM'08),
Pisa, Italy. June 2008.
Volume 5029 in Lecture Notes in Computer Science, pages 31–43. Springer
(original publication).
[show abstract]
Abstract.
We study the NPcomplete Graph Motif problem: given a
vertexcolored graph G = (V,E) and a multiset M of colors, does there
exist an S⊆V such that G[S] is connected and carries exactly (also
with respect to multiplicity) the colors in M? We present an improved
randomized algorithm for Graph Motif with running time O(4.32^{M} ·
M^{2} · E). We extend our algorithm to listcolored graph vertices and
the case where the motif G[S] needs not be connected. By way of contrast,
we show that extending the request for motif connectedness to the
somewhat 'more robust' motif demands of biconnectedness or bridgeconnectedness
leads to W[1]complete problems. Actually, we show that
the presumably simpler problems of finding (uncolored) biconnected or
bridgeconnected subgraphs are W[1]complete with respect to the subgraph
size. Answering an open question from the literature, we further
show that the parameter 'number of connected motif components' leads
to W[1]hardness even when restricted to graphs that are paths.

Jiong Guo,
Falk Hüffner,
Christian Komusiewicz, and
Yong Zhang:
Improved algorithms for bicluster editing.
In Proceedings of the 5th Annual Conference on Theory and Applications of Models of Computation
(TAMC'08),
Xian, China. April 2008.
Volume 4978 in Lecture Notes in Computer Science, pages 451–462, Springer
(original publication).
[show abstract]
Abstract.
The NPhard Bicluster Editing is to add
or remove at most k edges to make a bipartite graph a
vertexdisjoint union of complete bipartite subgraphs. It has
applications in the analysis of gene expression data. We show
that by polynomialtime preprocessing, one can shrink a problem
instance to one with 4k vertices, thus proving that the
problem has a linear kernel, improving a quadratic kernel
result. We further give a search tree algorithm that improves
the running time bound from the trivial
O(4^{k} + m) to
O(3.24^{k} + m). Finally, we give a
randomized 4approximation, improving a known approximation with
factor 11.

Falk Hüffner,
Christian Komusiewicz,
Hannes Moser, and
Rolf Niedermeier:
Enumerating isolated cliques in synthetic and financial networks.
In Proceedings of the 2nd Annual International Conference on Combinatorial Optimization and Applications
(COCOA'08),
St. John's, Newfoundland, Canada. August 2008.
Volume 5165 in Lecture Notes in Computer Science, pages 405–416, Springer
(original publication).
[show abstract]
Abstract.
We do computational studies concerning the
enumeration of maximal isolated cliques in graphs. Isolation,
as recently introduced, measures the degree of connectedness
of the cliques to the rest of the graph. Isolation helps both
in getting faster algorithms than for the enumeration of
maximal general cliques and in filtering out cliques with
special semantics. We perform experiments with synthetic
graphs (in the G_{n,m,p} model) and financial networks, proposing
the enumeration of isolated cliques as a useful instrument in
analyzing financial networks.

Falk Hüffner,
Christian Komusiewicz,
Hannes Moser, and
Rolf Niedermeier:
Fixedparameter algorithms for cluster vertex deletion.
In Proceedings of the 8th Latin American Theoretical Informatics Symposium
(LATIN'08),
Búzios, Brazil. April 2008.
Volume 4957 of Lecture Notes in Computer Science, pages 711–722, Springer
(original publication).
Journal version available.
[show abstract]
Abstract.
We initiate the first systematic study of the NPhard Cluster Vertex Deletion (CVD) problem
(unweighted and weighted) in terms of fixedparameter
algorithmics. Here one searches for a minimum number of vertex
deletions to transform a graph into a collection of cliques. The
parameter denotes the number of vertex deletions. We present
several efficient fixedparameter algorithms for CVD. Our
iterative compression algorithm for CVD seems to be the first
nontrivial application of this fairly new technique to a problem
that is not a feedback set problem. Moreover, we study the
variant of CVD where the number of cliques to be generated is
prespecified. Here, we detect surprising connections to
fixedparameter algorithms for (Weighted)
Vertex Cover.

Christian Komusiewicz, and
Johannes Uhlmann:
A cubicvertex kernel for flip consensus tree.
In Proceedings of the 28th Foundations of Software Technology and Theoretical Computer Science conference
(FSTTCS'08),
Bangalore, India. December 2008.
Volume 08004 of Dagstuhl Seminar Proceedings, pages 280–291, Internationales Begegnungs und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany(original publication).
[show abstract]
Abstract.
Given a bipartite graph G=(V_{c},V_{t},E) and a nonnegative integer k,
the NPcomplete MinimumFlip Consensus Tree problem
asks whether G can be transformed, using up to k edge insertions and deletions,
into a graph that does not contain an induced P_{5} with its first vertex
in V_{t} (a socalled Mgraph or Sigmagraph).
This problem plays an important role in computational phylogenetics, V_{c}
standing for the characters and V_{t} standing for taxa.
Chen et al. [IEEE/ACM TCBB 2006] showed that MinimumFlip Consensus Tree is NPcomplete and presented a
parameterized algorithm with running time O(6^{k}* V_{t}* V_{c}).
Recently, Böcker et al. [IWPEC '08] presented a refined search tree algorithm
with running time O(4.83^{k}(V_{t}+V_{c}) + V_{t}* V_{c}).
We complement these results by polynomialtime executable data reduction rules yielding
a problem kernel with O(k^{3}) vertices.

2007

Conference articles 

Christian Komusiewicz,
Falk Hüffner,
Hannes Moser, and
Rolf Niedermeier:
Isolation concepts for enumerating dense subgraphs.
In Proceedings of the 13th International Computing and Combinatorics Conference
(COCOON'07),
Banff, Canada. July 2007.
Volume 4598 in Lecture Notes in Computer Science, pages 140–150, Springer
(original publication).
[show abstract]
Abstract.
In a graph G = (V,E), a vertex subset
S⊆V of size k is called
cisolated if it has less than c·k outgoing
edges. We repair a nontrivially flawed algorithm for enumerating
all cisolated cliques due to Ito et al. [ESA 2005] and
obtain an algorithm running in
O(4^{c}·c^{4}·E)
time. We describe a speedup trick that also helps parallelizing
the enumeration. Moreover, we introduce a more restricted and a
more general isolation concept and show that both lead to faster
enumeration algorithms. Finally, we extend our considerations to
splexes (a relaxation of the clique notion), providing a
W[1]hardness result and a fixedparameter algorithm for
enumerating isolated splexes.

Theses 

Christian Komusiewicz:
Various Isolation Concepts for the Enumeration of Dense Subgraphs.
Diplomarbeit, Institut für Informatik,
FriedrichSchillerUniversität Jena, March 2007.
[show abstract]
Abstract.
We study algorithms for the enumeration of dense subgraphs. In
particular, we pair dense subgraphs with isolation concepts to obtain
efficient enumeration algorithms in spite of the NPhardness of
detecting these subgraphs. We discuss several types of dense
subgraphs with regard to their application in the analysis of
biological networks and provide complexity results for the problem of
detecting splexes, sclubs and scliques, when the respective
problems are parameterized with the size of the solution sets. We use
three different isolation concepts of which one is due to Ito et
al. [ESA 2005] and the other two are introduced in this work.
We repair a nontrivially flawed algorithm for enumerating all
cisolated cliques due to Ito et al. and show that
both our isolation concepts lead to faster enumeration algorithms for
cliques and can be also employed to obtain fixedparameter algorithms
for the enumeration of splexes and defective cliques.
