Approximation and hardness results for the maximum edges in transitive closure problem

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F15%3A00087423" target="_blank" >RIV/00216224:14330/15:00087423 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-319-19315-1_2" target="_blank" >http://dx.doi.org/10.1007/978-3-319-19315-1_2</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-19315-1_2" target="_blank" >10.1007/978-3-319-19315-1_2</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Approximation and hardness results for the maximum edges in transitive closure problem

Popis výsledku v původním jazyce

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 &gt; 0. Additionally, we show that the problem is APXhard already for the case when the numberof vertex colors equals 3. We complement these results by showing the first approximation algorithm for the problem, with approximation factor [formula presented]

Název v anglickém jazyce

Approximation and hardness results for the maximum edges in transitive closure problem

Popis výsledku anglicky

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 &gt; 0. Additionally, we show that the problem is APXhard already for the case when the numberof vertex colors equals 3. We complement these results by showing the first approximation algorithm for the problem, with approximation factor [formula presented]

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2015

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

25th International Workshop on Combinatorial Algorithms, IWOCA 2014, LNCS 8986

ISBN

9783319193144

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

11

Strana od-do

13-23

Název nakladatele

Springer

Místo vydání

Duluth; United States

Místo konání akce

Duluth; United States

Datum konání akce

1. 1. 2015

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—