On the hardness of labeled correlation clustering problem: A parameterized complexity view

Xianmin Liu; Jianzhong Li; Hong Gao

doi:10.1016/j.tcs.2015.03.021

On the hardness of labeled correlation clustering problem: A parameterized complexity view

Xianmin Liu
, Jianzhong Li^*
, Hong Gao

^*Corresponding author for this work

Faculty of Computing

Harbin Institute of Technology

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

Motivated by practical applications, the Labeled Correlation Clustering problem, a variant of Correlation Clustering problem, is formally defined and studied in this paper. Since the problem is NP- complete, we consider the parameterized complexities. Three different parameterizations are considered, and the corresponding parameterized complexities are studied. For the two parameterized problems which are fixed-parameter-tractable, the lower bounds of them are analyzed under SETH (Strong Exponential Time Hypothesis).

Original language	English
Pages (from-to)	583-593
Number of pages	11
Journal	Theoretical Computer Science
Volume	609
DOIs	https://doi.org/10.1016/j.tcs.2015.03.021
State	Published - 4 Jan 2016

Keywords

Labeled correlation clustering
Lower bound
Parameterized complexity
Strong Exponential Time Hypothesis

Access to Document

10.1016/j.tcs.2015.03.021

Cite this

@article{6f1c59cae943417193feaf1896b5153d,

title = "On the hardness of labeled correlation clustering problem: A parameterized complexity view",

abstract = "Motivated by practical applications, the Labeled Correlation Clustering problem, a variant of Correlation Clustering problem, is formally defined and studied in this paper. Since the problem is NP- complete, we consider the parameterized complexities. Three different parameterizations are considered, and the corresponding parameterized complexities are studied. For the two parameterized problems which are fixed-parameter-tractable, the lower bounds of them are analyzed under SETH (Strong Exponential Time Hypothesis).",

keywords = "Labeled correlation clustering, Lower bound, Parameterized complexity, Strong Exponential Time Hypothesis",

author = "Xianmin Liu and Jianzhong Li and Hong Gao",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier B.V.",

year = "2016",

month = jan,

day = "4",

doi = "10.1016/j.tcs.2015.03.021",

language = "英语",

volume = "609",

pages = "583--593",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - On the hardness of labeled correlation clustering problem

T2 - A parameterized complexity view

AU - Liu, Xianmin

AU - Li, Jianzhong

AU - Gao, Hong

PY - 2016/1/4

Y1 - 2016/1/4

N2 - Motivated by practical applications, the Labeled Correlation Clustering problem, a variant of Correlation Clustering problem, is formally defined and studied in this paper. Since the problem is NP- complete, we consider the parameterized complexities. Three different parameterizations are considered, and the corresponding parameterized complexities are studied. For the two parameterized problems which are fixed-parameter-tractable, the lower bounds of them are analyzed under SETH (Strong Exponential Time Hypothesis).

AB - Motivated by practical applications, the Labeled Correlation Clustering problem, a variant of Correlation Clustering problem, is formally defined and studied in this paper. Since the problem is NP- complete, we consider the parameterized complexities. Three different parameterizations are considered, and the corresponding parameterized complexities are studied. For the two parameterized problems which are fixed-parameter-tractable, the lower bounds of them are analyzed under SETH (Strong Exponential Time Hypothesis).

KW - Labeled correlation clustering

KW - Lower bound

KW - Parameterized complexity

KW - Strong Exponential Time Hypothesis

UR - https://www.scopus.com/pages/publications/84948799370

U2 - 10.1016/j.tcs.2015.03.021

DO - 10.1016/j.tcs.2015.03.021

M3 - 文章

AN - SCOPUS:84948799370

SN - 0304-3975

VL - 609

SP - 583

EP - 593

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

On the hardness of labeled correlation clustering problem: A parameterized complexity view

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this