Christian Komusiewicz

Abstract. We study the NP-complete Graph Motif problem: given a vertex-colored 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|² · |E|). We extend our algorithm to list-colored 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 bridge-connected 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.

Abstract. The NP-hard Bicluster Editing is to add or remove at most k edges to make a bipartite graph a vertex-disjoint union of complete bipartite subgraphs. It has applications in the analysis of gene expression data. We show that by polynomial-time 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 4-approximation, improving a known approximation with factor 11.

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.

Abstract. We initiate the first systematic study of the NP-hard Cluster Vertex Deletion (CVD) problem (unweighted and weighted) in terms of fixed-parameter 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 fixed-parameter 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 fixed-parameter algorithms for (Weighted) Vertex Cover.

Abstract. In a graph G = (V,E), a vertex subset S⊆V of size k is called c-isolated if it has less than c·k outgoing edges. We repair a nontrivially flawed algorithm for enumerating all c-isolated cliques due to Ito et al. [ESA 2005] and obtain an algorithm running in O(4^c·c⁴·|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 s-plexes (a relaxation of the clique notion), providing a W[1]-hardness result and a fixed-parameter algorithm for enumerating isolated s-plexes.

Abstract. Given a bipartite graph G=(V_c,V_t,E) and a non-negative integer k, the NP-complete Minimum-Flip 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₅ with its first vertex in V_t (a so-called M-graph or Sigma-graph). 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 \textsc{Minimum-Flip Consensus Tree} is NP-complete 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 polynomial-time executable data reduction rules yielding a problem kernel with O(k³) vertices.

Abstract. We initiate the first systematic study of the NP-hard Cluster Vertex Deletion (CVD) problem (unweighted and weighted) in terms of fixed-parameter 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 fixed-parameter 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 fixed-parameter algorithms for (weighted) Vertex Cover.

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 NP-hardness 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 s-plexes, s-clubs and s-cliques, 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 c-isolated 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 fixed-parameter algorithms for the enumeration of s-plexes and defective cliques.