
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 2008  Copyright 2008 Universität Bonn, Institut für Informatik, Abt. V  
85293 01.09.2008 
Approximating Transitivity in Directed Networks
Piotr Berman, Bhaskar DasGupta and Marek Karpinski [Download PostScript] [Download PDF] We study the problem of computing a minimum equivalent digraph(also known as the problem of computing a strong transitive reduction)and its maximum objective function variant, with two types of extensions.First, we allow to declare a set D ⊂ E and require that a valid solution Asatisfies D ⊂ A (it is sometimes called transitive reduction problem).In the second extension (called pary transitive reduction),we have integer edge labeling and we view two paths as equivalent if they havethe same beginning, ending and the sum of labels modulo p. A solutionA ⊆ E is valid if it gives an equivalent path for every original path.For all problems we establish the following: polynomial time minimization ofA within ratio 1.5, maximization of EA within ratio 2, MAXSNPhardness even of the length of simple cycles is limited to 5.Furthermore, we believe that the combinatorial technique behind theapproximation algorithm for the minimization version might be of interest toother graph connectivity problems as well. 

Last Change:
11/05/14 at 10:41:20
English 
Universität Bonn > Institut für Informatik > Abteilung V 