2015

Conference articles 

Journal articles (to appear) 

Robert Bredereck,
Jiehua Chen,
Sepp Hartung, Christian Komusiewicz,
Rolf Niedermeier, and
Ondřej Suchý:
On Explaining Integer Vectors by few Homogenous Segments.
Journal of Computer and System Sciences (original publication).

Jiehua Chen,
Christian Komusiewicz,
Rolf Niedermeier,
Manuel Sorge,
Ondřej Suchý, and
Mathias Weller :
Polynomialtime Data Reduction for the Subset Interconnection Design Problem.
SIAM
Journal on Discrete Mathematics (original publication).

Guillaume Fertin, Shahrad Jamshidi, and Christian Komusiewicz:
Towards an Algorithmic Guide to Spiral Galaxies.
Theoretical Computer Science.

Sepp
Hartung, Christian Komusiewicz,
André
Nichterlein, and
Ondřej Suchý :
On Structural Parameterizations for the 2Club Problem.
Discrete Applied Mathematics (original publication).

Christian Komusiewicz and Manuel Sorge:
An Algorithmic Framework for FixedCardinality Optimization in Sparse Graphs Applied to Dense Subgraph Problems.
Discrete Applied Mathematics.

Book chapters (to appear) 

Falk
Hüffner, Christian
Komusiewicz, Rolf
Niedermeier, and Sebastian Wernicke:
Parameterized
Algorithmics for Finding Exact Solutions of NPHard Biological
Problems. In: Bioinformatics Volume II: Structure, Function and Applications. Series: Methods in Molecular Biology, Springer.

Christian Komusiewicz:
Partially Polynomial Kernels.
In: Encyclopedia of Algorithms, Springer (original publication).

2014

Conference articles 

Sharon Bruckner,
Falk Hüffner, and
Christian Komusiewicz:
A Graph Modification Approach for Finding Core–Periphery Structures in Protein Interaction Networks.
In Proceedings of the 14th Workshop on Algorithms in Bioinformatics
(WABI'14), Wrocław, Poland, September 2014. Volume 8701 in Lecture Notes in Computer Science (subseries Lecture Notes in Bioinformatics), pages 340–351, Springer (original publication).

Laurent Bulteau,
Guillaume Fertin, and Christian Komusiewicz:
Reversal Distances for Strings with Few Blocks or Small Alphabets.
In Proceedings of the 25th Annual Symposium on Combinatorial Pattern Matching
(CPM'14), Moscow, Russia, June 2014. Volume 8486 in Lecture Notes in Computer Science, pages 50–59, Springer (original publication).

Laurent Bulteau and Christian Komusiewicz:
Minimum Common String Partition Parameterized by Partition Size is FixedParameter Tractable.
In Proceedings of the 25th ACMSIAM Symposion on Discrete Algorithms
(SODA'14), Portland, Oregon, January 2014. Pages 102–121, SIAM (original publication).

Guillaume Fertin, Shahrad Jamshidi, and Christian Komusiewicz:
Towards an Algorithmic Guide to Spiral Galaxies.
In Proceedings of the Seventh International Conference on Fun with Algorithms
(FUN'14), Lipari Island, Italy, July 2014. Volume 8496 in Lecture Notes in Computer Science, pages 171–182, Springer (original publication).

Falk
Hüffner, Christian
Komusiewicz, Rolf
Niedermeier, and Martin Rötzschke:
The Parameterized Complexity of the Rainbow Subgraph
Problem. In Proceedings of the 40th
International Workshop on GraphTheoretic Concepts in
Computer Science
(WG'14),
Domaine de Chalès, France, June 2014.
Volume 8747 in Lecture Notes in Computer Science, pages 287–298, Springer (original publication).

Journal articles 

Laurent Bulteau,
Falk Hüffner,
Christian Komusiewicz, and
Rolf Niedermeier:
Multivariate Algorithmics for NPhard String Problems.
Bulletin of the EATCS 114:31–73, 2014 ( original publication).

Martin Dörnfelder,
Jiong Guo,
Christian Komusiewicz, and
Mathias Weller:
On the Parameterized Complexity of Consensus Clustering.
Theoretical Computer Science 542: 71–82, 2014 (original publication).

Jiong Guo,
Danny Hermelin, and
Christian Komusiewicz:
Local
Search for String Problems: BruteForce is Essentially Optimal.
Theoretical Computer Science 525:30–41, 2014 (original
publication).

Falk Hüffner,
Christian Komusiewicz, Adrian Liebtrau, and
Rolf Niedermeier:
Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage.
IEEE/ACM Transactions on Computational Biology and Bioinformatics. 11(3): 455–467, 2014 (original publication).
 Christian Komusiewicz and
Johannes Uhlmann:
A CubicVertex Kernel for Flip Consensus Tree.
Algorithmica 68(1):81–108, 2014 (original publication).

2013

Conference articles 

Robert Bredereck,
Jiehua Chen,
Sepp Hartung, Christian Komusiewicz,
Rolf Niedermeier, and
Ondřej Suchý:
On Explaining Integer Vectors by few Homogenous Segments.
In Proceedings of the Algorithms and Data Structures Symposium
(WADS'13), London, Ontario, Canada, August 2013.
Volume 8037 in Lecture Notes in Computer Science, pages 207–218, Springer (original publication).

Sharon Bruckner,
Falk Hüffner,
Christian Komusiewicz, and
Rolf Niedermeier:
Evaluation of ILPbased Approaches for Partitioning into Colorful Components.
In Proceedings of the 12th International Symposium on Experimental Algorithms
(SEA'13), Rome, Italy, June 2013. Volume 7933 in Lecture Notes in Computer Science, pages 176–187, Springer (original publication).

Laurent Bulteau,
Guillaume Fertin, Christian Komusiewicz, and Irena Rusu :
A FixedParameter Algorithm for Minimum Common String Partition with Few Duplications.
In Proceedings of the 13th Workshop on Algorithms in Bioinformatics
(WABI'13), Sophia Antipolis, France, September 2013. Volume 8126 in Lecture Notes in Computer Science (subseries Lecture Notes in Bioinformatics), pages 244–258, Springer.

Jiehua Chen,
Christian Komusiewicz,
Rolf Niedermeier,
Manuel Sorge,
Ondřej Suchý, and
Mathias Weller :
Effective and Efficient Data Reduction for the Subset Interconnection Design Problem.
In Proceedings of the 24th International Symposium on Algorithms and Computation
(ISAAC'13), Hong Kong, China, December 2013.
Lecture Notes in Computer Science, Springer.

Jiong Guo,
Danny Hermelin, and Christian Komusiewicz:
Local Search for String Problems: BruteForce is Essentially Optimal.
In Proceedings of the 24th Annual Symposium on Combinatorial Pattern Matching
(CPM'13), Bad Herrenalb, Germany, June 2013. Volume 7922 in Lecture Notes in Computer Science, pages 130–141, Springer (original publication).

Sepp Hartung, Christian Komusiewicz, and
André Nichterlein:
On Structural Parameterizations for the 2Club Problem.
In Proceedings of the 39th International Conference on Current Trends
in Theory and Practice of Computer Science
(SOFSEM'13), Špindlerův Mlýn, Czech Republic, January 2013. Volume 7741 in Lecture Notes in Computer Science, pages 233–243, Springer (original publication).

Falk Hüffner,
Christian Komusiewicz, Adrian Liebtrau, and
Rolf Niedermeier:
Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage.
In Proceedings of the 9th International Symposium on
Bioinformatics Research and Applications
(ISBRA'13), Charlotte, USA, May 2013. Volume 7875 in Lecture Notes in Computer Science (subseries Lecture Notes in Bioinformatics), pages 99–111, Springer (original publication).

2012

Conference articles 

Sharon Bruckner,
Falk Hüffner,
Christian Komusiewicz,
Rolf Niedermeier,
Sven Thiel,
and
Johannes Uhlmann:
Partitioning into Colorful Components by Minimum Edge Deletions.
In Proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching
(CPM'12), Helsinki, Finland, June 2012. Volume 7354 in Lecture Notes in Computer Science, pages 56–69, Springer (original publication).

Leo Brueggeman,
Michael R. Fellows,
Rudolf Fleischer,
Martin Lackner,
Christian Komusiewicz,
Yiannis Koutis,
Andreas Pfandler, and
Frances Rosamond:
Train Marshalling is Fixed Parameter Tractable.
In Proceedings of the Sixth International Conference on Fun with Algorithms
(FUN'12),
Venice, Italy, June 2012.
Volume 7288 in Lecture Notes in Computer Science, pages 51–56, Springer (original publication).

Sepp Hartung, Christian Komusiewicz and
André Nichterlein:
Parameterized Algorithmics and Computational Experiments for Finding 2Clubs.
In Proceedings of the 7th International Symposium on Parameterized and Exact Computation
(IPEC'12), Ljubljana, Slovenia, September 2012. Volume 7535 in Lecture Notes in Computer Science, pages 231–241, Springer (original publication).

Christian Komusiewicz and Rolf Niedermeier:
New Races in Parameterized Algorithmics.
In Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science
(MFCS'12), Bratislava, Slovakia, August 2012.
Volume 7464 in Lecture Notes in Computer Science, pages 19–30, Springer (original publication).

Christian Komusiewicz and
Manuel Sorge:
Finding Dense Subgraphs of Sparse Graphs.
In Proceedings of the 7th International Symposium on Parameterized and Exact Computation
(IPEC'12), Ljubljana, Slovenia, September 2012. Volume 7535 in Lecture Notes in Computer Science, pages 242–251, Springer (original publication).

Journal articles 
 Christian Komusiewicz and
Johannes Uhlmann:
Cluster Editing with Locally Bounded Modifications.
Discrete Applied Mathematics 160(15):2259–2270, 2012 (original publication).
 Alexander Schäfer,
Christian Komusiewicz,
Hannes Moser, and
Rolf
Niedermeier:
Parameterized Computational Complexity of Finding SmallDiameter Subgraphs.
Optimization Letters 6(5):883–891, 2012 (original publication).
 Christoph Schmidt, Thomas Weiss, Christian Komusiewicz, Herbert Witte, and Lutz Leistritz:
An Analytical Approach to Network Motif Detection in Samples of Networks with Pairwise Different Vertex Labels.
Computational and Mathematical Methods in Medicine, Volume 2012, Article ID 910380 (original publication).

Mathias Weller,
Christian Komusiewicz,
Rolf Niedermeier, and
Johannes Uhlmann:
On Making Directed Graphs Transitive.
Journal of Computer and System Sciences 78(2):559–574, 2012 (original publication).

2011

Conference articles 

Martin Dörnfelder,
Jiong Guo,
Christian Komusiewicz, and
Mathias Weller:
On the Parameterized Complexity of Consensus Clustering.
In Proceedings of the 22nd International Symposium on Algorithms and Computation
(ISAAC'11),
Yokohama, Japan, December 2011.
Volume 7074 in Lecture Notes in Computer Science, pages 624–633, Springer (original publication).

Christian Komusiewicz and
Johannes Uhlmann:
Alternative Parameterizations for Cluster Editing.
In Proceedings of the 37th International Conference on Current Trends in Theory and Practice of Computer Science
(SOFSEM'11),
Nový Smokovec, Slovakia, January 2011.
Volume 6543 in Lecture Notes in Computer Science, pages 344–355, Springer
(original publication).

Journal articles 

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 8(5):1296–1308, 2011 (original publication).

Nadja Betzler,
Jiong Guo,
Christian Komusiewicz, and
Rolf Niedermeier:
Average Parameterization and Partial Kernelization for Computing Medians.
Journal of Computer and System Sciences 77(4):774–789, 2011 (original publication).

Michael R. Fellows,
Jiong Guo,
Christian Komusiewicz,
Rolf Niedermeier, and
Johannes Uhlmann:
Graphbased data clustering with overlaps.
Discrete Optimization 8(1):2–17, 2011 (original publication).

Jiong Guo,
Iyad A. Kanj,
Christian Komusiewicz, and
Johannes Uhlmann:
Editing Graphs into Disjoint Unions of Dense Clusters.
Algorithmica 61(4):949–970,
2011 (original publication).

Christian Komusiewicz,
Rolf Niedermeier, and
Johannes Uhlmann:
Deconstructing
Intractability – A Multivariate Complexity Analysis of
Interval Constrained Coloring.
Journal of Discrete Algorithms 9(1):137–151,
2011
(original publication).

Thesis 

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
(original publication) .

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 

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 24(4):
1662–1683, 2010
(original
publication).

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.

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.

Thesis 

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.
