Graph-based data clustering with overlaps

Michael Fellows, Jiong Guo, Christian Komusiewicz, Rolf Niedermeier, Johannes Uhlmann

    Research output: Contribution to journalArticleResearchpeer-review

    Abstract

    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).
    Original languageEnglish
    Pages (from-to)2-17
    Number of pages16
    JournalDiscrete Optimization
    Volume8
    Issue number1
    DOIs
    Publication statusPublished - 2011

    Fingerprint

    Data Clustering
    Overlap
    Hardness
    Polynomials
    Graph in graph theory
    Maximal Clique
    Fixed-parameter Tractability
    Forbidden Subgraph
    Parameterized Complexity
    Dichotomy
    Vertex of a graph
    Polynomial time
    NP-complete problem
    Target

    Cite this

    Fellows, M., Guo, J., Komusiewicz, C., Niedermeier, R., & Uhlmann, J. (2011). Graph-based data clustering with overlaps. Discrete Optimization, 8(1), 2-17. https://doi.org/10.1016/j.disopt.2010.09.006
    Fellows, Michael ; Guo, Jiong ; Komusiewicz, Christian ; Niedermeier, Rolf ; Uhlmann, Johannes. / Graph-based data clustering with overlaps. In: Discrete Optimization. 2011 ; Vol. 8, No. 1. pp. 2-17.
    @article{dae11a29a3cd46408a3d3045cb00690a,
    title = "Graph-based data clustering with overlaps",
    abstract = "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).",
    keywords = "Fixed-parameter tractability, Forbidden subgraph characterization, Graph modifications, Kernelization, NP-hardness, W [1]-hardness, Characterization, Hardness, Parameter estimation, Clustering algorithms",
    author = "Michael Fellows and Jiong Guo and Christian Komusiewicz and Rolf Niedermeier and Johannes Uhlmann",
    year = "2011",
    doi = "10.1016/j.disopt.2010.09.006",
    language = "English",
    volume = "8",
    pages = "2--17",
    journal = "Discrete Optimization",
    issn = "1572-5286",
    publisher = "Elsevier",
    number = "1",

    }

    Fellows, M, Guo, J, Komusiewicz, C, Niedermeier, R & Uhlmann, J 2011, 'Graph-based data clustering with overlaps', Discrete Optimization, vol. 8, no. 1, pp. 2-17. https://doi.org/10.1016/j.disopt.2010.09.006

    Graph-based data clustering with overlaps. / Fellows, Michael; Guo, Jiong; Komusiewicz, Christian; Niedermeier, Rolf; Uhlmann, Johannes.

    In: Discrete Optimization, Vol. 8, No. 1, 2011, p. 2-17.

    Research output: Contribution to journalArticleResearchpeer-review

    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

    VL - 8

    SP - 2

    EP - 17

    JO - Discrete Optimization

    JF - Discrete Optimization

    SN - 1572-5286

    IS - 1

    ER -

    Fellows M, Guo J, Komusiewicz C, Niedermeier R, Uhlmann J. Graph-based data clustering with overlaps. Discrete Optimization. 2011;8(1):2-17. https://doi.org/10.1016/j.disopt.2010.09.006