Clustering with partial information

H Bodlaender, Michael Fellows, P Heggernes, F Mancini, C Papadopoulos, F Rosamond

Research output: Contribution to journalArticleResearchpeer-review

Abstract

The Correlation Clustering problem, also known as the Cluster Editing problem, seeks to edit a given graph by adding and deleting edges to obtain a collection of vertex-disjoint cliques, such that the editing cost is minimized. The Edge Clique Partitioning problem seeks to partition the edges of a given graph into edge-disjoint cliques, such that the number of cliques is minimized. Both problems are known to be NP-hard, and they have been previously studied with respect to approximation and fixed-parameter tractability. In this paper we study these two problems in a more general setting that we term fuzzy graphs, where the input graphs may have missing information, meaning that whether or not there is an edge between some pairs of vertices of the input graph can be undecided.
For fuzzy graphs the Correlation Clustering and Edge Clique Partitioning problems have previously been studied only with respect to approximation. Here we give parameterized algorithms based on kernelization for both problems. We prove that the Correlation Clustering problem is fixed-parameter tractable on fuzzy graphs when parameterized (k, r) by , where k is the editing cost and r is the minimum number of vertices required to cover the undecided edges. In particular we show that it has a polynomial-time reduction to a problem kernel on O (k2 + r)  vertices. We provide an analogous result for the Edge Clique Partitioning problem on fuzzy graphs. Using (k, r) as parameters, where  k bounds the size of the partition, and r is the minimum number of vertices required to cover the undecided edges, we describe a polynomial-time kernelization to a problem kernel on O (k4 • 3r) vertices. This implies fixed-parameter tractability for this parameterization. Furthermore we also show that parameterizing only by the number of cliques , is not enough to obtain fixed-parameter tractability. The problem remains, in fact, NP-hard for each fixed k>2.
Original languageEnglish
Pages (from-to)1202-1211
Number of pages10
JournalTheoretical Computer Science
Volume411
Issue number7-9
DOIs
Publication statusPublished - 2010
Externally publishedYes

Fingerprint

Partial Information
Polynomials
Clustering
Clique
Parameterization
Fuzzy Graph
Costs
Fixed-parameter Tractability
Kernelization
Partitioning
Graph in graph theory
Polynomial time
Disjoint
NP-complete problem
Partition
Cover
kernel
Parameterized Algorithms
Approximation

Cite this

Bodlaender, H., Fellows, M., Heggernes, P., Mancini, F., Papadopoulos, C., & Rosamond, F. (2010). Clustering with partial information. Theoretical Computer Science, 411(7-9), 1202-1211. https://doi.org/10.1016/j.tcs.2009.12.016
Bodlaender, H ; Fellows, Michael ; Heggernes, P ; Mancini, F ; Papadopoulos, C ; Rosamond, F. / Clustering with partial information. In: Theoretical Computer Science. 2010 ; Vol. 411, No. 7-9. pp. 1202-1211.
@article{04495b5fbb5c4bc9971d346e7b793c42,
title = "Clustering with partial information",
abstract = "The Correlation Clustering problem, also known as the Cluster Editing problem, seeks to edit a given graph by adding and deleting edges to obtain a collection of vertex-disjoint cliques, such that the editing cost is minimized. The Edge Clique Partitioning problem seeks to partition the edges of a given graph into edge-disjoint cliques, such that the number of cliques is minimized. Both problems are known to be NP-hard, and they have been previously studied with respect to approximation and fixed-parameter tractability. In this paper we study these two problems in a more general setting that we term fuzzy graphs, where the input graphs may have missing information, meaning that whether or not there is an edge between some pairs of vertices of the input graph can be undecided.For fuzzy graphs the Correlation Clustering and Edge Clique Partitioning problems have previously been studied only with respect to approximation. Here we give parameterized algorithms based on kernelization for both problems. We prove that the Correlation Clustering problem is fixed-parameter tractable on fuzzy graphs when parameterized (k, r) by , where k is the editing cost and r is the minimum number of vertices required to cover the undecided edges. In particular we show that it has a polynomial-time reduction to a problem kernel on O (k2 + r)  vertices. We provide an analogous result for the Edge Clique Partitioning problem on fuzzy graphs. Using (k, r) as parameters, where  k bounds the size of the partition, and r is the minimum number of vertices required to cover the undecided edges, we describe a polynomial-time kernelization to a problem kernel on O (k4 • 3r) vertices. This implies fixed-parameter tractability for this parameterization. Furthermore we also show that parameterizing only by the number of cliques , is not enough to obtain fixed-parameter tractability. The problem remains, in fact, NP-hard for each fixed k>2.",
author = "H Bodlaender and Michael Fellows and P Heggernes and F Mancini and C Papadopoulos and F Rosamond",
year = "2010",
doi = "10.1016/j.tcs.2009.12.016",
language = "English",
volume = "411",
pages = "1202--1211",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "7-9",

}

Bodlaender, H, Fellows, M, Heggernes, P, Mancini, F, Papadopoulos, C & Rosamond, F 2010, 'Clustering with partial information', Theoretical Computer Science, vol. 411, no. 7-9, pp. 1202-1211. https://doi.org/10.1016/j.tcs.2009.12.016

Clustering with partial information. / Bodlaender, H; Fellows, Michael; Heggernes, P; Mancini, F; Papadopoulos, C; Rosamond, F.

In: Theoretical Computer Science, Vol. 411, No. 7-9, 2010, p. 1202-1211.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Clustering with partial information

AU - Bodlaender, H

AU - Fellows, Michael

AU - Heggernes, P

AU - Mancini, F

AU - Papadopoulos, C

AU - Rosamond, F

PY - 2010

Y1 - 2010

N2 - The Correlation Clustering problem, also known as the Cluster Editing problem, seeks to edit a given graph by adding and deleting edges to obtain a collection of vertex-disjoint cliques, such that the editing cost is minimized. The Edge Clique Partitioning problem seeks to partition the edges of a given graph into edge-disjoint cliques, such that the number of cliques is minimized. Both problems are known to be NP-hard, and they have been previously studied with respect to approximation and fixed-parameter tractability. In this paper we study these two problems in a more general setting that we term fuzzy graphs, where the input graphs may have missing information, meaning that whether or not there is an edge between some pairs of vertices of the input graph can be undecided.For fuzzy graphs the Correlation Clustering and Edge Clique Partitioning problems have previously been studied only with respect to approximation. Here we give parameterized algorithms based on kernelization for both problems. We prove that the Correlation Clustering problem is fixed-parameter tractable on fuzzy graphs when parameterized (k, r) by , where k is the editing cost and r is the minimum number of vertices required to cover the undecided edges. In particular we show that it has a polynomial-time reduction to a problem kernel on O (k2 + r)  vertices. We provide an analogous result for the Edge Clique Partitioning problem on fuzzy graphs. Using (k, r) as parameters, where  k bounds the size of the partition, and r is the minimum number of vertices required to cover the undecided edges, we describe a polynomial-time kernelization to a problem kernel on O (k4 • 3r) vertices. This implies fixed-parameter tractability for this parameterization. Furthermore we also show that parameterizing only by the number of cliques , is not enough to obtain fixed-parameter tractability. The problem remains, in fact, NP-hard for each fixed k>2.

AB - The Correlation Clustering problem, also known as the Cluster Editing problem, seeks to edit a given graph by adding and deleting edges to obtain a collection of vertex-disjoint cliques, such that the editing cost is minimized. The Edge Clique Partitioning problem seeks to partition the edges of a given graph into edge-disjoint cliques, such that the number of cliques is minimized. Both problems are known to be NP-hard, and they have been previously studied with respect to approximation and fixed-parameter tractability. In this paper we study these two problems in a more general setting that we term fuzzy graphs, where the input graphs may have missing information, meaning that whether or not there is an edge between some pairs of vertices of the input graph can be undecided.For fuzzy graphs the Correlation Clustering and Edge Clique Partitioning problems have previously been studied only with respect to approximation. Here we give parameterized algorithms based on kernelization for both problems. We prove that the Correlation Clustering problem is fixed-parameter tractable on fuzzy graphs when parameterized (k, r) by , where k is the editing cost and r is the minimum number of vertices required to cover the undecided edges. In particular we show that it has a polynomial-time reduction to a problem kernel on O (k2 + r)  vertices. We provide an analogous result for the Edge Clique Partitioning problem on fuzzy graphs. Using (k, r) as parameters, where  k bounds the size of the partition, and r is the minimum number of vertices required to cover the undecided edges, we describe a polynomial-time kernelization to a problem kernel on O (k4 • 3r) vertices. This implies fixed-parameter tractability for this parameterization. Furthermore we also show that parameterizing only by the number of cliques , is not enough to obtain fixed-parameter tractability. The problem remains, in fact, NP-hard for each fixed k>2.

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

U2 - 10.1016/j.tcs.2009.12.016

DO - 10.1016/j.tcs.2009.12.016

M3 - Article

VL - 411

SP - 1202

EP - 1211

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 7-9

ER -

Bodlaender H, Fellows M, Heggernes P, Mancini F, Papadopoulos C, Rosamond F. Clustering with partial information. Theoretical Computer Science. 2010;411(7-9):1202-1211. https://doi.org/10.1016/j.tcs.2009.12.016