On Strongly Connected Digraphs with Bounded Cycle Length
| dc.contributor.author | Khuller, Samir | en_US |
| dc.contributor.author | Raghavachari, Balaji | en_US |
| dc.contributor.author | Young, Neal | en_US |
| dc.date.accessioned | 2004-05-31T22:25:04Z | |
| dc.date.available | 2004-05-31T22:25:04Z | |
| dc.date.created | 1994-01 | en_US |
| dc.date.issued | 1998-10-15 | en_US |
| dc.description.abstract | The MEG (minimum equivalent graph) problem is "Given a directed graph, find a smallest subset of the edges that maintains all reachability relations between nodes." We consider the complexity of this problem as a function of the maximum cycle length C in the graph. If C =2, the problem is trivial. Recently it was shown that even with the restriction C = 5, the problem is NP-hard. It was conjectured that the problem is solvable in polynomial time if C =3. In this paper we prove the conjecture, showing that the problem is equivalent to maximum bipartite matching. The strong dependence of the complexity on the cycle length is in marked contrast to the relation of complexity and cycle length in undirected graphs. Undirected graphs with bounded cycle length have bounded tree width, allowing polynomial-time algorithms for many problems that are NP-hard in general. A consequence of our result is an improved approximation algorithm for the MEG problem in general graphs. The improved algorithm has a performance guarantee of about 1.61; the best previous algorithm has a performance guarantee of about 1.64. (Also cross-referenced as UMIACS-TR-94-10) | en_US |
| dc.format.extent | 206242 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/615 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-3212 | en_US |
| dc.relation.ispartofseries | UMIACS; UMIACS-TR-94-10 | en_US |
| dc.title | On Strongly Connected Digraphs with Bounded Cycle Length | en_US |
| dc.type | Technical Report | en_US |