TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 19.07.2017b

isti-logo

Page Content

to Navigation

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.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe