Algorithmic and Hardness Results for the Colorful Components
Problems

D 2014

Algorithmic and Hardness Results for the Colorful Components Problems

ADAMASZEK, Anna a Alexandru POPA

Základní údaje

Originální název

Algorithmic and Hardness Results for the Colorful Components Problems

Autoři

ADAMASZEK, Anna a Alexandru POPA

Vydání

Berlin, 11th Latin American Theoretical Informatics Symposium, LATIN 2014, od s. 683-694, 12 s. 2014

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/14:00080117

Organizační jednotka

Fakulta informatiky

ISBN

978-3-642-54422-4

ISSN

DOI

https://doi.org/10.1007/978-3-642-54423-1_59

UT WoS

000342804300059

EID Scopus

2-s2.0-84899969783

Klíčová slova anglicky

Algorithms; Information science; Polynomial approximation

Štítky

core_B, firank_B

Změněno: 28. 4. 2015 13:06, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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 C' 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 not equal 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 vertical bar V vertical bar(1/14-epsilon) for any epsilon > 0, assuming P not equal NP (or within a factor of vertical bar V vertical bar(1/2-epsilon), assuming ZPP not equal NP).

Návaznosti

EE2.3.30.0009, projekt VaV

Název: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci

Citovat

ADAMASZEK, Anna a Alexandru POPA. Algorithmic and Hardness Results for the Colorful Components Problems. In 11th Latin American Theoretical Informatics Symposium, LATIN 2014. Berlin: Springer, 2014, s. 683-694. ISBN 978-3-642-54422-4. Dostupné z: https://doi.org/10.1007/978-3-642-54423-1_59.

@inproceedings{1298543,
   author = {Adamaszek, Anna and Popa, Alexandru},
   address = {Berlin},
   booktitle = {11th Latin American Theoretical Informatics Symposium, LATIN 2014},
   doi = {https://doi.org/10.1007/978-3-642-54423-1_59},
   keywords = {Algorithms; Information science; Polynomial approximation},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Berlin},
   isbn = {978-3-642-54422-4},
   pages = {683-694},
   publisher = {Springer},
   title = {Algorithmic and Hardness Results for the Colorful Components Problems},
   year = {2014}
}

TY  - CONF
ID  - 1298543
AU  - Adamaszek, Anna - Popa, Alexandru
PY  - 2014
TI  - Algorithmic and Hardness Results for the Colorful Components Problems
PB  - Springer
CY  - Berlin
SN  - 9783642544224
KW  - Algorithms
KW  - Information science
KW  - Polynomial approximation
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 C' 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 not equal 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 vertical bar V vertical bar(1/14-epsilon) for any epsilon > 0, assuming P not equal NP (or within a factor of vertical bar V vertical bar(1/2-epsilon), assuming ZPP not equal NP).
ER  -

ADAMASZEK, Anna a Alexandru POPA. Algorithmic and Hardness Results for the Colorful Components Problems. In \textit{11th Latin American Theoretical Informatics Symposium, LATIN 2014}. Berlin: Springer, 2014, s.~683-694. ISBN~978-3-642-54422-4. Dostupné z: https://doi.org/10.1007/978-3-642-54423-1\_{}59.

Přehled o publikaci