Christian Komusiewicz

• Source code in C++

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 show that the problem to decide whether a graph can be made triangle-free with at most k edge deletions remains NP-complete even when restricted to planar graphs of maximum degree seven. In addition, we provide polynomial-time data reduction rules for this problem and obtain problem kernels consisting of 6k vertices for general graphs and 11k/3 vertices for planar graphs.

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 s-vertex overlap, each vertex may be part of at most s maximal cliques; s-edge overlap is analogously defined in terms of edges. We provide a complete complexity dichotomy (polynomial-time solvable vs NP-complete) 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 fixed-parameter tractability results (in case of constant s-values) and parameterized hardness (in case of unbounded s-values).

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 well-studied 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 (s-defective cliques), 2) having average degree at least |V_K|-s (average-s-plexes), 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 NP-complete for all three density measures. Then, we study the fixed-parameter tractability of the three clustering problems, showing that the first two problems are fixed-parameter 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.

Abstract. We introduce the s-Plex Editing problem generalizing the well-studied Cluster Editing problem, both being NP-hard and both being motivated by graph-based 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 s-Plex Editing is now to transform a graph into a disjoint union of so-called s-plexes. Herein, an s-plex denotes a vertex set inducing a (sub)graph where every vertex has edges to all but at most s vertices in the s-plex. Cliques are 1-plexes. The advantage of s-plexes for s≥2 is that they allow to model a more relaxed cluster notion (s-plexes 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 so-called problem kernel), a forbidden subgraph characterization of s-plex cluster graphs, and a depth-bounded search tree which is used to find optimal edge modification sets. Altogether, this yields efficient algorithms in case of moderate numbers of edge modifications.

Abstract. The NP-hard 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 NP-hardness 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 (fixed-parameter) tractability results and, moreover, identify a large spectrum of combinatorial research challenges for Interval Constrained Coloring.

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 NP-hard. We correct this error by presenting a first proof of NP-hardness, which also extends to the restricted cases where the input digraph is acyclic or has maximum degree four. Moreover, we improve previous fixed-parameter algorithms, now achieving a running time of O(2.57 ^k + n³) for an n-vertex digraph if k arc modifications are sufficient to make it transitive. In particular, providing an O(k²)-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 NP-hardness) can be transferred to the Transitivity Deletion problem, where only arc deletions are allowed.

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 fixed-parameter 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).

Abstract. In an undirected graph G = (V, E), a set of k vertices is called c-isolated if it has less than c · k outgoing edges. Ito and Iwama [ACM Trans. Algorithms, to appear] gave an algorithm to enumerate all c-isolated maximal cliques in O(4^c · c⁴ · |E|) time. We extend this to enumerating all maximal c-isolated 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 s-plexes (a relaxation of the clique notion), providing a W[1]-hardness result when the size of the s-plex is the parameter and a fixed-parameter algorithm for enumerating isolated s-plexes when the parameter describes the degree of isolation.

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. 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 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. 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. 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.