Algorithmic and Hardness Results for the Colorful Components Problems

Logo poskytovatele

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

ADAMASZEK Anna POPA Alexandru

Rok publikování 2014
Druh Článek ve sborníku
Konference 11th Latin American Theoretical Informatics Symposium, LATIN 2014
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
Doi http://dx.doi.org/10.1007/978-3-642-54423-1_59
Obor Informatika
Klíčová slova Algorithms; Information science; Polynomial approximation
Popis 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).
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.