Multivariate Algorithmics

Research

We are interested in the design and analysis exact algorithms for NP-hard problems. To obtain efficient algorithms despite exponential worst-case running time, we follow the approach of multivariate algorithmics. Here, the idea is to identify small problem-specific parameters and design algorithms where the exponential running time part depends on only on the parameter and not on the overall instance size. Starting from a complexity analysis of a problem, our aim is to obtain exact algorithms that have low worst-case running time and are fast in practice.

Graph Clustering

In graph clustering we want to partition a given network into cohesive subgroups, called clusters, that interact heavily with each other and only weakly with the other subgroups. These partitions can be used, for example, to identify functional units of a network.

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.

Clique Relaxations

Clique relaxations are cohesive or dense subgraphs that can be used to identify communities in networks. Finding large occurrences of such clique relaxations in a graph is usually hard. Our aim is to obtain efficient algorithms for the most relevant clique relaxations.

Christian Komusiewicz: Multivariate Algorithmics for Finding Cohesive Subnetworks. Algorithms 9(1): 21, 2016.

Team

Principal Investigator

Dr. Christian Komusiewicz

+49 3641 946316
Ernst-Abbe-Platz 2, Room 3315
Picture of Christian Komusiewicz

Jobs

Student Research Assistants

We are looking for students that are interested in implementing and tuning graph algorithms. Applicants should have a basic knowledge in algorithms and experience in a common programming language (preferably Java or C++).
If you are interested, please contact Christian Komusiewicz .

Theses

We are looking for bachelor and master students that are interested in algorithmic research on network and string problems. Topics range from algorithm engineering projects, where the aim is to implement and improve algorithms for a computational problem on a given set of instances to computational complexity studies where we are looking for new algorithms or algorithmic lower bounds. Two example projects are described below. Bachelor theses are usually more implementation-oriented and master theses more theory-driven but this is not a must.

Bachelor Thesis Project

Finding all connected subnetworks of a fixed size in an input network is a fundamental computational task that is a subroutine of many algorithms. Several different algorithms for this task are described in the literature but, so far, a systematic comparison is lacking. The goal of the thesis would be to implement 2–3 of these algorithms and to compare their performance on benchmark instances.

Master Thesis Project

In a network, highly connected sets of nodes correspond to cohesive groups, for example groups of friends in Facebook or a protein complexes in protein interaction networks. One definition of highly connected is that at least half of the group members must be removed to disconnect the group. Finding such groups is an NP-hard problem. The aim of the project would be to find out how network properties influence the difficulty of this problem.

If you are interested in this type of topics, please contact Christian Komusiewicz . Usually, we propose 2–3 different topics; the thesis can be written in german or english.

Publications

2017

Conference Articles

Journal Articles

2016

Conference Articles

Journal Articles

2015

Conference Articles

Journal Articles

Book chapters

  • Falk Hüffner, Christian Komusiewicz, Rolf Niedermeier, and Sebastian Wernicke: Parameterized Algorithmics for Finding Exact Solutions of NP-Hard 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

Journal Articles

2013

Conference Articles

2012

Conference Articles

Journal Articles

2011

Conference Articles

Journal Articles

Thesis

2010

Conference Articles

Journal Articles

2009

Conference Articles

Journal Articles

2008

Conference Articles

2007

Conference Articles

Thesis

  • Christian Komusiewicz: Various Isolation Concepts for the Enumeration of Dense Subgraphs. Diplomarbeit, Institut für Informatik, Friedrich-Schiller-Universität Jena, March 2007.

Contact

Dr. Christian Komusiewicz
Institut für Informatik
Fakultät für Mathematik und Informatik
Friedrich-Schiller-Universität Jena
Ernst-Abbe-Platz 2
D-07743 Jena

+49 3641 946316
Room 3315