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

computational complexity.

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.

comp.theory.

Thank you very much in advance and Ciao

- Jan Overbeck -

===========================================================================

Jan Overbeck

Vienna Technical University

Institute for Information Systems

Paniglgasse 16

A-1040 Vienna, Austria

Tel. : (+43)-1-58801-6141

Fax : (+43)-1-505-5304

========================================================================