Algorithmic and Hardness Results for the Colorful Components Problems

Anna Adamaszek, Alexandru Popa

Research output: Contribution to journalArticle

5 Citations (Scopus)

Abstract

In this paper we investigate the colorful components framework, motivated by applications emerging from comparative genomics. The general goal is to remove a collection of edges from an undirected vertex-colored graph G such that in the resulting graph (Formula Presented.) all the connected components are colorful (i.e., any two vertices of the same color belong to different connected components). We want (Formula Presented.) to optimize an objective function, the selection of this function being specific to each problem in the framework. We analyze three objective functions, and thus, three different problems, which are believed to be relevant for the biological applications: minimizing the number of singleton vertices, maximizing the number of edges in the transitive closure, and minimizing the number of connected components. Our main result is a polynomial-time algorithm for the first problem. This result disproves the conjecture of Zheng et al. that the problem is NP-hard (assuming P ≠ NP). Then, we show that the second problem is APX-hard, thus proving and strengthening the conjecture of Zheng et al. that the problem is NP-hard. Finally, we show that the third problem does not admit polynomial-time approximation within a factor of (Formula Presented.) for any (Formula Presented.), assuming (Formula Presented.) (or within a factor of (Formula Presented.), assuming (Formula Presented.)).

Original languageEnglish
Pages (from-to)371-388
Number of pages18
JournalAlgorithmica
Volume73
Issue number2
DOIs
Publication statusPublished - Aug 15 2014
Externally publishedYes

Fingerprint

Hardness
Computational complexity
Polynomials
Connected Components
Color
NP-complete problem
Objective function
Colored Graph
Transitive Closure
Comparative Genomics
Disprove
Strengthening
Polynomial-time Algorithm
Polynomial time
Optimise
Approximation
Graph in graph theory
Vertex of a graph
Genomics

Keywords

  • Colorful components
  • Exact polynomial-time algorithms
  • Graph coloring
  • Hardness of approximation

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Cite this

Algorithmic and Hardness Results for the Colorful Components Problems. / Adamaszek, Anna; Popa, Alexandru.

In: Algorithmica, Vol. 73, No. 2, 15.08.2014, p. 371-388.

Research output: Contribution to journalArticle

Adamaszek, Anna ; Popa, Alexandru. / Algorithmic and Hardness Results for the Colorful Components Problems. In: Algorithmica. 2014 ; Vol. 73, No. 2. pp. 371-388.
@article{31722d025fe54137b5a1dbd1ba506175,
title = "Algorithmic and Hardness Results for the Colorful Components Problems",
abstract = "In this paper we investigate the colorful components framework, motivated by applications emerging from comparative genomics. The general goal is to remove a collection of edges from an undirected vertex-colored graph G such that in the resulting graph (Formula Presented.) all the connected components are colorful (i.e., any two vertices of the same color belong to different connected components). We want (Formula Presented.) to optimize an objective function, the selection of this function being specific to each problem in the framework. We analyze three objective functions, and thus, three different problems, which are believed to be relevant for the biological applications: minimizing the number of singleton vertices, maximizing the number of edges in the transitive closure, and minimizing the number of connected components. Our main result is a polynomial-time algorithm for the first problem. This result disproves the conjecture of Zheng et al. that the problem is NP-hard (assuming P ≠ NP). Then, we show that the second problem is APX-hard, thus proving and strengthening the conjecture of Zheng et al. that the problem is NP-hard. Finally, we show that the third problem does not admit polynomial-time approximation within a factor of (Formula Presented.) for any (Formula Presented.), assuming (Formula Presented.) (or within a factor of (Formula Presented.), assuming (Formula Presented.)).",
keywords = "Colorful components, Exact polynomial-time algorithms, Graph coloring, Hardness of approximation",
author = "Anna Adamaszek and Alexandru Popa",
year = "2014",
month = "8",
day = "15",
doi = "10.1007/s00453-014-9926-0",
language = "English",
volume = "73",
pages = "371--388",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer New York",
number = "2",

}

TY - JOUR

T1 - Algorithmic and Hardness Results for the Colorful Components Problems

AU - Adamaszek, Anna

AU - Popa, Alexandru

PY - 2014/8/15

Y1 - 2014/8/15

N2 - In this paper we investigate the colorful components framework, motivated by applications emerging from comparative genomics. The general goal is to remove a collection of edges from an undirected vertex-colored graph G such that in the resulting graph (Formula Presented.) all the connected components are colorful (i.e., any two vertices of the same color belong to different connected components). We want (Formula Presented.) to optimize an objective function, the selection of this function being specific to each problem in the framework. We analyze three objective functions, and thus, three different problems, which are believed to be relevant for the biological applications: minimizing the number of singleton vertices, maximizing the number of edges in the transitive closure, and minimizing the number of connected components. Our main result is a polynomial-time algorithm for the first problem. This result disproves the conjecture of Zheng et al. that the problem is NP-hard (assuming P ≠ NP). Then, we show that the second problem is APX-hard, thus proving and strengthening the conjecture of Zheng et al. that the problem is NP-hard. Finally, we show that the third problem does not admit polynomial-time approximation within a factor of (Formula Presented.) for any (Formula Presented.), assuming (Formula Presented.) (or within a factor of (Formula Presented.), assuming (Formula Presented.)).

AB - In this paper we investigate the colorful components framework, motivated by applications emerging from comparative genomics. The general goal is to remove a collection of edges from an undirected vertex-colored graph G such that in the resulting graph (Formula Presented.) all the connected components are colorful (i.e., any two vertices of the same color belong to different connected components). We want (Formula Presented.) to optimize an objective function, the selection of this function being specific to each problem in the framework. We analyze three objective functions, and thus, three different problems, which are believed to be relevant for the biological applications: minimizing the number of singleton vertices, maximizing the number of edges in the transitive closure, and minimizing the number of connected components. Our main result is a polynomial-time algorithm for the first problem. This result disproves the conjecture of Zheng et al. that the problem is NP-hard (assuming P ≠ NP). Then, we show that the second problem is APX-hard, thus proving and strengthening the conjecture of Zheng et al. that the problem is NP-hard. Finally, we show that the third problem does not admit polynomial-time approximation within a factor of (Formula Presented.) for any (Formula Presented.), assuming (Formula Presented.) (or within a factor of (Formula Presented.), assuming (Formula Presented.)).

KW - Colorful components

KW - Exact polynomial-time algorithms

KW - Graph coloring

KW - Hardness of approximation

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

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

U2 - 10.1007/s00453-014-9926-0

DO - 10.1007/s00453-014-9926-0

M3 - Article

VL - 73

SP - 371

EP - 388

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 2

ER -