Detailed Information on Publication Record
2015
Approximation and hardness results for the maximum edges in transitive closure problem
ADAMASZEK, Anna, G. BLIN and Alexandru POPABasic information
Original name
Approximation and hardness results for the maximum edges in transitive closure problem
Authors
ADAMASZEK, Anna (616 Poland), G. BLIN (250 France) and Alexandru POPA (642 Romania, belonging to the institution)
Edition
Duluth; United States, 25th International Workshop on Combinatorial Algorithms, IWOCA 2014, LNCS 8986, p. 13-23, 11 pp. 2015
Publisher
Springer
Other information
Language
English
Type of outcome
Stať ve sborníku
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
Switzerland
Confidentiality degree
není předmětem státního či obchodního tajemství
Publication form
printed version "print"
Impact factor
Impact factor: 0.402 in 2005
RIV identification code
RIV/00216224:14330/15:00087423
Organization unit
Faculty of Informatics
ISBN
978-3-319-19314-4
ISSN
UT WoS
000365044500002
Keywords in English
Algorithms; Bioinformatics; Combinatorial mathematics; Graph theory; Hardness
Změněno: 6/5/2016 06:14, RNDr. Pavel Šmerk, Ph.D.
Abstract
V originále
In this paper we study the following problem, named Maximum Edges in Transitive Closure, which has applications in computational biology. Given a simple, undirected graph G = (V,E) and a coloring of the vertices, remove a collection of edges from the graph such that each connected component is colorful (i.e., it does not contain two identically colored vertices) and the number of edges in the transitive closure of the graph is maximized. The problem is known to be APX-hard, and no approximation algorithms are known for it. We improve the hardness result by showing that the problem is NP-hard to approximate within a factor of |V |1/3-eps, for any constant eps > 0. Additionally, we show that the problem is APXhard already for the case when the number of vertex colors equals 3. We complement these results by showing the first approximation algorithm for the problem, with approximation factor [formula presented]