Find a DAG in a str. conn. graph

Find a DAG in a str. conn. graph

Post by Jan Overbe » Thu, 27 Jan 1994 22:56:44

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.


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