×

A more relaxed model for graph-based data clustering: \(s\)-plex cluster editing. (English) Zbl 1221.05293

Summary: We introduce the \(s\)-Plex Cluster Editing problem as a generalization of the well-studied Cluster Editing problem; both are NP-hard and both are 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 (this is Cluster Editing), the task in the case of \(s\)-Plex Cluster Editing is to transform a graph into a cluster graph consisting of a disjoint union of so-called \(s\)-plexes. Herein, an \(s\)-plex is a vertex set \(S\) inducing a subgraph in which every vertex has degree at least \(|S|-s\). Cliques are 1-plexes.
The advantage of \(s\)-plexes for \(s\geq2\) is that they allow us to model a more relaxed cluster notion (\(s\)-plexes instead of cliques), better reflecting inaccuracies of the input data. We develop a provably 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; this is often a reasonable assumption under a maximum parsimony model for data clustering.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
68W99 Algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI