Sie sind hier

# 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ý

Date
Speaker
Location
Language
19.07.2017
17:00
Hendrik Molter
TEL 512
English

Back to the research colloquium site.