From: hermann@uran.informatik.uni-bonn.de (Hermann Stamm)
Subject: Re: Help: Algorithm for Cyclic -> Acyclic Graph?
Reply-To: hermann@uran.informatik.uni-bonn.de (Hermann Stamm)
Organization: Praktische Informatik III
Date: Thu, 1 Oct 1992 07:21:08 GMT

Hello!

In article <1acjrbINNnsa@frigate.doc.ic.ac.uk> you write:
|> Hi! I am a PhD student in Imperial College and I am looking for a fast
|> graph algorithm to solve the following graph problem.
|> 
|> Given a cyclic digraph with a special root node in the graph, reduce
|> the cyclic graph into an acyclic digraph by removing the MINIMUM number
|> of edges but all the nodes reachable by the root node in the cyclic
|> graph must also remain REACHABLE by the root node in the acyclic
|> graph.
|> 
|> E.g.
|>                -------X
|>                |      ^
|>                v      |
|> Cyclic Graph:  S ---> X ----> X 
|>                       ^       |
|>                       |       |
|>                       ---------
|> 	where S is the root node and Xs are common nodes.
|> 
|>                       X
|>                       ^
|>                       |
|> Acyclic Graph: S ---> X ----> X 
|> 
|> Another E.g.
|>                ------>X
|>                |      |
|>                |      v
|> Cyclic Graph:  S ---> X ----> X 
|>                       ^       |
|>                       |       |
|>                       ---------
|>                                
|>                ------>X
|>                |      |
|>                |      v
|> Acyclic Graph: S ---> X ----> X 
|>                                
|> My present solution is:
|> 1) Work out an acyclic graph from the cyclic graph using DFS.
|> 2) Work out the topological order in the acyclic graph. 
|> 3) For each node in the cyclic graph (using the topological order)
|>      Propagate a tag from the node in the cyclic graph and remove those
|>      edges which propagate the tag back to the node.
|> 
|> However, I am not sure whether the algorithm removes the minimum number
|> of edges and whether there is a better standard algorithm.
|> 
|> Please reply by email.
|> 
|> Thank you.
|> 
|> S.C. Cheung (scc@doc.ic.ac.uk)
|> -- 
|> 	SC Cheung	(scc@doc.ic.ac.uk  071-589 5111 ext 5092)


Sorry, an efficient algorithm for this problem seems to be unlikely, because
this problem (call it PR) is NP-complete.
The only help for you can lie in that your graphs are i.e. planar, since
FAS(planar) is solvable in polynomial time.


The proof is simly done by reducing the "normal" (NP-complete) FAS-problem 
to it, which is:

Input:     digraph D=(V,A), K>0
Question:  exists A' \subset A, |A'|<=K, with D-A' being acyclic ?


That PR is in NP is easy.
Now let D=(V,A) and K>0 be an instance of FAS (V={v1,...,vn}).

Construct a new digraph E=(W,B) with W={S,v1,...,vn} and
B = A u { (S,vi) | 1<=i<=n }.

Now let E and K (and S) be the instance of PR. 
Any solution A' of FAS(D) is also a solution of PR(E), since
the new arcs (B-A) don't introduce new cycles, and any vertex 
is reachable from S by the arcs of B-A.
If A" is a solution of PR(E), then B-A" is acyclic, and thus
A" \cap A is a solution for FAS(D).


Hope this helps,

   Hermann.
Newsgroups: comp.theory