direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

A Parameterized View on Multi-Layer Cluster Editing

Hendrik Molter (TU Berlin)

In classical Cluster Editing we seek to transform a given graph into a disjoint union of cliques called a cluster graph, using the fewest number of edge modifications (deletions or additions). Motivated by recent applications, we propose and study Cluster Editing in multi-layer graphs. A multi-layer graph consists of a set of simple graphs, called layers, that all have the same vertex set. In Multi-Layer Cluster Editing we aim to transform all layers into cluster graphs which do not differ too much. More specifically, we allow to mark at most (d)​ vertices and to transform each layer of the multi-layer graph into a cluster graph with at most (k)​ edge modifications per layer such that, if we remove the marked vertices, we get the same cluster graph in all layers. Multi-Layer Cluster Editing is NP-hard and we analyze its parameterized complexity. We focus on the natural parameters “max. number d​ of marked vertices”, “max. number (k)​ of edge modifications per layer”, “number (n​) of vertices”, and “number (l) of layers” and fully explore the parameterized computational complexity landscape for those parameters and their combinations. Our main results are that Multi-Layer Cluster Editing is FPT with respect to the parameter combination ((d, k)​) and that it is para-NP-hard for all smaller or incomparable parameter combinations. Furthermore, we give a polynomial kernel with respect to the parameter combination ((d, k, l))​ and show that for all smaller or incomparable parameter combinations, the problem does not admit a polynomial kernel unless NP ⊆ coNP/poly.


This is a joint work with Jiehua Chen, Manuel Sorge, and Ondřej Suchý


Hendrik Molter
TEL 512

Back to the research colloquium site. [1]

------ Links: ------

Zusatzinformationen / Extras