# Parameterized Algorithms for the 2-Clustering Problem with Minimum Sum and Minimum Sum of Squares Objective Functions

Ontology type: schema:ScholarlyArticle      Open Access: True

### Article Info

DATE

2014-02-07

AUTHORS ABSTRACT

In the Min-Sum 2-Clustering problem, we are given a graph and a parameter k, and the goal is to determine if there exists a 2-partition of the vertex set such that the total conflict number is at most k, where the conflict number of a vertex is the number of its non-neighbors in the same cluster and neighbors in the different cluster. The problem is equivalent to 2-Cluster Editing and 2-Correlation Clustering with an additional multiplicative factor two in the cost function. In this paper we show an algorithm for Min-Sum 2-Clustering with time complexity O(n⋅2.619r/(1−4r/n)+n3), where n is the number of vertices and r=k/n. Particularly, the time complexity is O∗(2.619k/n) for k∈o(n2) and polynomial for k∈O(nlogn), which implies that the problem can be solved in subexponential time for k∈o(n2). We also design a parameterized algorithm for a variant in which the cost is the sum of the squared conflict-numbers. For k∈o(n3), the algorithm runs in subexponential O(n3⋅5.171θ) time, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\theta=\sqrt{k/n}$\end{document}. More... »

PAGES

818-835

### References to SciGraph publications

• 2009. Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms in PARAMETERIZED AND EXACT COMPUTATION
• 2003-05-13. Graph-Modeled Data Clustering: Fixed-Parameter Algorithms for Clique Generation in ALGORITHMS AND COMPLEXITY
• 2004-03-19. Automated Generation of Search Tree Algorithms for Hard Graph Modification Problems in ALGORITHMICA
• 2010. Exact Exponential Algorithms in NONE
• 2008-07-16. Fixed-Parameter Enumerability of Cluster Editing and Related Problems in THEORY OF COMPUTING SYSTEMS
• 2008-10-15. Fixed-Parameter Algorithms for Cluster Vertex Deletion in THEORY OF COMPUTING SYSTEMS
• 2004-07. Correlation Clustering in MACHINE LEARNING
• 1999. Parameterized Complexity in NONE
• 2013. On the Min-Max 2-Cluster Editing Problem in ADVANCES IN INTELLIGENT SYSTEMS AND APPLICATIONS - VOLUME 1
• 2007-01-01. Optimal Edge Deletions for Signed Graph Balancing in EXPERIMENTAL ALGORITHMS

TITLE

Algorithmica

ISSUE

3

VOLUME

72

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-014-9874-8

DOI

http://dx.doi.org/10.1007/s00453-014-9874-8

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1051438401

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Artificial Intelligence and Image Processing",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "National Chung Cheng University, 621, ChiaYi, Taiwan, ROC",
"id": "http://www.grid.ac/institutes/grid.412047.4",
"name": [
"National Chung Cheng University, 621, ChiaYi, Taiwan, ROC"
],
"type": "Organization"
},
"familyName": "Wu",
"givenName": "Bang Ye",
"id": "sg:person.013045767237.23",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "National Chung Cheng University, 621, ChiaYi, Taiwan, ROC",
"id": "http://www.grid.ac/institutes/grid.412047.4",
"name": [
"National Chung Cheng University, 621, ChiaYi, Taiwan, ROC"
],
"type": "Organization"
},
"familyName": "Chen",
"givenName": "Li-Hsuan",
"id": "sg:person.014055212561.22",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014055212561.22"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/978-3-642-35452-6_16",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1032367522",
"https://doi.org/10.1007/978-3-642-35452-6_16"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-1-4612-0515-9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1050354225",
"https://doi.org/10.1007/978-1-4612-0515-9"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00224-008-9150-x",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1032458581",
"https://doi.org/10.1007/s00224-008-9150-x"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-16533-7",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1012209190",
"https://doi.org/10.1007/978-3-642-16533-7"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-44849-7_17",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1000170504",
"https://doi.org/10.1007/3-540-44849-7_17"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1023/b:mach.0000033116.57574.95",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1005313049",
"https://doi.org/10.1023/b:mach.0000033116.57574.95"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00224-008-9130-1",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1035666083",
"https://doi.org/10.1007/s00224-008-9130-1"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00453-004-1090-5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1051624082",
"https://doi.org/10.1007/s00453-004-1090-5"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-11269-0_8",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1022401414",
"https://doi.org/10.1007/978-3-642-11269-0_8"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-72845-0_23",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1026860505",
"https://doi.org/10.1007/978-3-540-72845-0_23"
],
"type": "CreativeWork"
}
],
"datePublished": "2014-02-07",
"datePublishedReg": "2014-02-07",
"description": "In the Min-Sum 2-Clustering problem, we are given a graph and a parameter k, and the goal is to determine if there exists a 2-partition of the vertex set such that the total conflict number is at most k, where the conflict number of a vertex is the number of its non-neighbors in the same cluster and neighbors in the different cluster. The problem is equivalent to 2-Cluster Editing and 2-Correlation Clustering with an additional multiplicative factor two in the cost function. In this paper we show an algorithm for Min-Sum 2-Clustering with time complexity O(n\u22c52.619r/(1\u22124r/n)+n3), where n is the number of vertices and r=k/n. Particularly, the time complexity is O\u2217(2.619k/n) for k\u2208o(n2) and polynomial for k\u2208O(nlogn), which implies that the problem can be solved in subexponential time for k\u2208o(n2). We also design a parameterized algorithm for a variant in which the cost is the sum of the squared conflict-numbers. For k\u2208o(n3), the algorithm runs in subexponential O(n3\u22c55.171\u03b8) time, where \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\theta=\\sqrt{k/n}$\\end{document}.",
"genre": "article",
"id": "sg:pub.10.1007/s00453-014-9874-8",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": [
{
"id": "sg:journal.1047644",
"issn": [
"0178-4617",
"1432-0541"
],
"name": "Algorithmica",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "3",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
}
],
"keywords": [
"time complexity",
"minimum sum",
"conflict number",
"subexponential time",
"number of vertices",
"algorithm",
"same cluster",
"cost function",
"objective function",
"different clusters",
"squares objective function",
"complexity",
"vertices",
"graph",
"neighbors",
"editing",
"clusters",
"number",
"cost",
"parameter k",
"goal",
"sum",
"time",
"polynomials",
"factor two",
"function",
"variants",
"two",
"problem",
"paper",
"Min-Sum 2-Clustering problem",
"total conflict number",
"multiplicative factor two",
"Min-Sum 2-Clustering"
],
"name": "Parameterized Algorithms for the 2-Clustering Problem with Minimum Sum and Minimum Sum of Squares Objective Functions",
"pagination": "818-835",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1051438401"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00453-014-9874-8"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00453-014-9874-8",
"https://app.dimensions.ai/details/publication/pub.1051438401"
],
"sdDataset": "articles",
"sdDatePublished": "2021-12-01T19:32",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/article/article_641.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00453-014-9874-8"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00453-014-9874-8'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00453-014-9874-8'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-014-9874-8'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-014-9874-8'

This table displays all metadata directly associated to this object as RDF triples.

140 TRIPLES      22 PREDICATES      70 URIs      52 LITERALS      6 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0801
3 schema:author N02eeb60c500d4178854227730e40b465
4 schema:citation sg:pub.10.1007/3-540-44849-7_17
5 sg:pub.10.1007/978-1-4612-0515-9
6 sg:pub.10.1007/978-3-540-72845-0_23
7 sg:pub.10.1007/978-3-642-11269-0_8
8 sg:pub.10.1007/978-3-642-16533-7
9 sg:pub.10.1007/978-3-642-35452-6_16
10 sg:pub.10.1007/s00224-008-9130-1
11 sg:pub.10.1007/s00224-008-9150-x
12 sg:pub.10.1007/s00453-004-1090-5
13 sg:pub.10.1023/b:mach.0000033116.57574.95
14 schema:datePublished 2014-02-07
15 schema:datePublishedReg 2014-02-07
16 schema:description In the Min-Sum 2-Clustering problem, we are given a graph and a parameter k, and the goal is to determine if there exists a 2-partition of the vertex set such that the total conflict number is at most k, where the conflict number of a vertex is the number of its non-neighbors in the same cluster and neighbors in the different cluster. The problem is equivalent to 2-Cluster Editing and 2-Correlation Clustering with an additional multiplicative factor two in the cost function. In this paper we show an algorithm for Min-Sum 2-Clustering with time complexity O(n⋅2.619r/(1−4r/n)+n3), where n is the number of vertices and r=k/n. Particularly, the time complexity is O∗(2.619k/n) for k∈o(n2) and polynomial for k∈O(nlogn), which implies that the problem can be solved in subexponential time for k∈o(n2). We also design a parameterized algorithm for a variant in which the cost is the sum of the squared conflict-numbers. For k∈o(n3), the algorithm runs in subexponential O(n3⋅5.171θ) time, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\theta=\sqrt{k/n}$\end{document}.
17 schema:genre article
18 schema:inLanguage en
19 schema:isAccessibleForFree true
20 schema:isPartOf N1d466c6c043344968396150ed1aca829
21 Ne6dac30428a54a129c338db701a3d3f0
22 sg:journal.1047644
23 schema:keywords Min-Sum 2-Clustering
24 Min-Sum 2-Clustering problem
26 algorithm
27 clusters
28 complexity
29 conflict number
30 cost
31 cost function
32 different clusters
33 editing
34 factor two
35 function
36 goal
37 graph
38 minimum sum
39 multiplicative factor two
40 neighbors
41 number
42 number of vertices
43 objective function
44 paper
45 parameter k
46 polynomials
47 problem
48 same cluster
49 squares objective function
50 subexponential time
51 sum
52 time
53 time complexity
54 total conflict number
55 two
56 variants
57 vertices
58 schema:name Parameterized Algorithms for the 2-Clustering Problem with Minimum Sum and Minimum Sum of Squares Objective Functions
59 schema:pagination 818-835
60 schema:productId N074e434b8b2442d198d512497480c20f
61 N8a2b997fdc8843bdb504347f4b38fb2b
62 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051438401
63 https://doi.org/10.1007/s00453-014-9874-8
64 schema:sdDatePublished 2021-12-01T19:32
66 schema:sdPublisher N21b3f21e4e514fc980d8695ddbb592a6
67 schema:url https://doi.org/10.1007/s00453-014-9874-8
69 sgo:sdDataset articles
70 rdf:type schema:ScholarlyArticle
71 N02eeb60c500d4178854227730e40b465 rdf:first sg:person.013045767237.23
72 rdf:rest Nb74c2b7976e34b69a48f48a834454c75
73 N074e434b8b2442d198d512497480c20f schema:name dimensions_id
74 schema:value pub.1051438401
75 rdf:type schema:PropertyValue
77 rdf:type schema:PublicationVolume
78 N21b3f21e4e514fc980d8695ddbb592a6 schema:name Springer Nature - SN SciGraph project
79 rdf:type schema:Organization
80 N8a2b997fdc8843bdb504347f4b38fb2b schema:name doi
81 schema:value 10.1007/s00453-014-9874-8
82 rdf:type schema:PropertyValue
83 Nb74c2b7976e34b69a48f48a834454c75 rdf:first sg:person.014055212561.22
84 rdf:rest rdf:nil
85 Ne6dac30428a54a129c338db701a3d3f0 schema:issueNumber 3
86 rdf:type schema:PublicationIssue
87 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
88 schema:name Information and Computing Sciences
89 rdf:type schema:DefinedTerm
90 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
91 schema:name Artificial Intelligence and Image Processing
92 rdf:type schema:DefinedTerm
93 sg:journal.1047644 schema:issn 0178-4617
94 1432-0541
95 schema:name Algorithmica
96 schema:publisher Springer Nature
97 rdf:type schema:Periodical
98 sg:person.013045767237.23 schema:affiliation grid-institutes:grid.412047.4
99 schema:familyName Wu
100 schema:givenName Bang Ye
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23
102 rdf:type schema:Person
103 sg:person.014055212561.22 schema:affiliation grid-institutes:grid.412047.4
104 schema:familyName Chen
105 schema:givenName Li-Hsuan
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014055212561.22
107 rdf:type schema:Person
108 sg:pub.10.1007/3-540-44849-7_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000170504
109 https://doi.org/10.1007/3-540-44849-7_17
110 rdf:type schema:CreativeWork
111 sg:pub.10.1007/978-1-4612-0515-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050354225
112 https://doi.org/10.1007/978-1-4612-0515-9
113 rdf:type schema:CreativeWork
114 sg:pub.10.1007/978-3-540-72845-0_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026860505
115 https://doi.org/10.1007/978-3-540-72845-0_23
116 rdf:type schema:CreativeWork
117 sg:pub.10.1007/978-3-642-11269-0_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022401414
118 https://doi.org/10.1007/978-3-642-11269-0_8
119 rdf:type schema:CreativeWork
120 sg:pub.10.1007/978-3-642-16533-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012209190
121 https://doi.org/10.1007/978-3-642-16533-7
122 rdf:type schema:CreativeWork
123 sg:pub.10.1007/978-3-642-35452-6_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032367522
124 https://doi.org/10.1007/978-3-642-35452-6_16
125 rdf:type schema:CreativeWork
126 sg:pub.10.1007/s00224-008-9130-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035666083
127 https://doi.org/10.1007/s00224-008-9130-1
128 rdf:type schema:CreativeWork
129 sg:pub.10.1007/s00224-008-9150-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1032458581
130 https://doi.org/10.1007/s00224-008-9150-x
131 rdf:type schema:CreativeWork
132 sg:pub.10.1007/s00453-004-1090-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051624082
133 https://doi.org/10.1007/s00453-004-1090-5
134 rdf:type schema:CreativeWork
135 sg:pub.10.1023/b:mach.0000033116.57574.95 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005313049
136 https://doi.org/10.1023/b:mach.0000033116.57574.95
137 rdf:type schema:CreativeWork
138 grid-institutes:grid.412047.4 schema:alternateName National Chung Cheng University, 621, ChiaYi, Taiwan, ROC
139 schema:name National Chung Cheng University, 621, ChiaYi, Taiwan, ROC
140 rdf:type schema:Organization