TY - JOUR

T1 - Graph-based data clustering with overlaps

AU - Fellows, Michael

AU - Guo, Jiong

AU - Komusiewicz, Christian

AU - Niedermeier, Rolf

AU - Uhlmann, Johannes

PY - 2011

Y1 - 2011

N2 - We introduce overlap cluster graph modification problems where, other than in most previous works, 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 (that is, 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 complexity dichotomy (polynomial-time solvable versus NP-hard) 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 (in case of constant s-values) and parameterized hardness (in case of unbounded s-values).

AB - We introduce overlap cluster graph modification problems where, other than in most previous works, 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 (that is, 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 complexity dichotomy (polynomial-time solvable versus NP-hard) 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 (in case of constant s-values) and parameterized hardness (in case of unbounded s-values).

KW - Fixed-parameter tractability

KW - Forbidden subgraph characterization

KW - Graph modifications

KW - Kernelization

KW - NP-hardness

KW - W [1]-hardness

KW - Characterization

KW - Hardness

KW - Parameter estimation

KW - Clustering algorithms

UR - http://www.scopus.com/inward/record.url?scp=79952186886&partnerID=8YFLogxK

U2 - 10.1016/j.disopt.2010.09.006

DO - 10.1016/j.disopt.2010.09.006

M3 - Article

SN - 1572-5286

VL - 8

SP - 2

EP - 17

JO - Discrete Optimization

JF - Discrete Optimization

IS - 1

ER -