Algorithmic and hardness results for the colorful components problems

Anna Adamaszek, Alexandru Popa

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 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 G' all the connected components are colorful (i.e., any two vertices of the same color belong to different connected components). We want G' 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 |V |1/14?∈ for any ∈ > 0, assuming P ≠ NP (or within a factor of |V

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Verlag
Pages683-694
Number of pages12
Volume8392 LNCS
ISBN (Print)9783642544224
DOIs
Publication statusPublished - 2014
Externally publishedYes
Event11th Latin American Theoretical Informatics Symposium, LATIN 2014 - Montevideo, Uruguay
Duration: Mar 31 2014Apr 4 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8392 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other11th Latin American Theoretical Informatics Symposium, LATIN 2014
CountryUruguay
CityMontevideo
Period3/31/144/4/14

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

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this

Adamaszek, A., & Popa, A. (2014). Algorithmic and hardness results for the colorful components problems. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 8392 LNCS, pp. 683-694). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8392 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-54423-1_59

Algorithmic and hardness results for the colorful components problems. / Adamaszek, Anna; Popa, Alexandru.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 8392 LNCS Springer Verlag, 2014. p. 683-694 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8392 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Adamaszek, A & Popa, A 2014, Algorithmic and hardness results for the colorful components problems. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). vol. 8392 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8392 LNCS, Springer Verlag, pp. 683-694, 11th Latin American Theoretical Informatics Symposium, LATIN 2014, Montevideo, Uruguay, 3/31/14. https://doi.org/10.1007/978-3-642-54423-1_59
Adamaszek A, Popa A. Algorithmic and hardness results for the colorful components problems. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 8392 LNCS. Springer Verlag. 2014. p. 683-694. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-54423-1_59
Adamaszek, Anna ; Popa, Alexandru. / Algorithmic and hardness results for the colorful components problems. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 8392 LNCS Springer Verlag, 2014. pp. 683-694 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{f21844ef93e04e0c89a45eeddce0e76f,
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 G' all the connected components are colorful (i.e., any two vertices of the same color belong to different connected components). We want G' 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 |V |1/14?∈ for any ∈ > 0, assuming P ≠ NP (or within a factor of |V",
author = "Anna Adamaszek and Alexandru Popa",
year = "2014",
doi = "10.1007/978-3-642-54423-1_59",
language = "English",
isbn = "9783642544224",
volume = "8392 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "683--694",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
address = "Germany",

}

TY - GEN

T1 - Algorithmic and hardness results for the colorful components problems

AU - Adamaszek, Anna

AU - Popa, Alexandru

PY - 2014

Y1 - 2014

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 G' all the connected components are colorful (i.e., any two vertices of the same color belong to different connected components). We want G' 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 |V |1/14?∈ for any ∈ > 0, assuming P ≠ NP (or within a factor of |V

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 G' all the connected components are colorful (i.e., any two vertices of the same color belong to different connected components). We want G' 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 |V |1/14?∈ for any ∈ > 0, assuming P ≠ NP (or within a factor of |V

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

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

U2 - 10.1007/978-3-642-54423-1_59

DO - 10.1007/978-3-642-54423-1_59

M3 - Conference contribution

SN - 9783642544224

VL - 8392 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 683

EP - 694

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

PB - Springer Verlag

ER -