I am looking for a solution to a problem, that I would describe in
abbreviated form as:
Find a maximum covering DAG in a strongly connected directed graph.
In more detail, the problem is as follows:
A strongly connected directed graph is a directed graph, where a path
exists betwen any pair of nodes. I want to delete a minimum set of
arcs (if not possible, a minimal set) to get a DAG, i.e. the set of
deleted arcs should have the property, that none of the arcs may be
inserted into the graph without introducing a cycle (minimal) and no
other set with less cardinality exists (minimum).
I need an algorithm for the problem and, if possible, a reference to an
article or book introducing the algorithm and discussing its
I assume, a polynomial algorithm for this problem exists, because it
seems to be of similar difficulty as the problem of finding a minimum
spanning tree in an weighted undirected graph with arc weights in the
real numbers (by setting all arc weights to -1).
I am no expert in graph theory, so I hope there exists a solution well
known in the community of graph algorithm experts.
Thank you very much in advance and Ciao
- Jan Overbeck -
Vienna Technical University
Institute for Information Systems
A-1040 Vienna, Austria
Tel. : (+43)-1-58801-6141
Fax : (+43)-1-505-5304