Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #244

Re: How to remove circles from a directed graph?

Show all headers | View raw

On Apr 7, 9:14 pm, Xu Wang <wangxu.n...@Use-Author-Supplied-
Address.invalid> wrote:
> Hello, everyone,
>
> I am trying to solve the following problem, but have not found any solution.
>
> For a directed graph, there are several circles. How to eliminate all
> circles to let the graph become acyclic by removing minimal numbers of arcs?
>
> I tried with set cover problem, hit problem, and so on. However, these
> methods are NP-complete. Is there any linear time complicity method for
> this problem?
>
> Thank you.
> Regards,
> Xu

Perhaps the best solution (and one that is not NP complete) is to
avoid adding cycles in the first place. I encountered this problem
when tracing dependencies in software.

As you build the graph, keep an auxiliary hash table containing one
entry for each distinct node. Before adding a node, check the table.
If the node is not found, add it. Otherwise do nothing.

A variant of this algorithm could be used to check a pre-existing
graph. Use recursion starting with the root node, for each node
visited see if it's in the table.

Not NP complete unless you screw up the hash.

There MAY be implications in this problem wrt 2008's financial panic,
for there are indications that credit reinsurance policies insured
themselves through indirect paths, using graphs with cyclicals
unchecked by software in the above manner.

Back to comp.programming | Previous | Next — Previous in thread | Find similar

Thread

How to remove circles from a directed graph? Xu Wang <wangxu.name@Use-Author-Supplied-Address.invalid> - 2011-04-07 15:14 +0200
  Re: How to remove circles from a directed graph? Damien Wyart <damien.wyart@free.fr> - 2011-04-07 17:35 +0200
    Re: How to remove circles from a directed graph? Damien Wyart <damien.wyart@free.fr> - 2011-04-07 20:26 +0200
    Re: How to remove circles from a directed graph? Damien Wyart <damien.wyart@free.fr> - 2011-04-07 20:42 +0200
  Re: How to remove circles from a directed graph? spinoza1111 <spinoza1111@yahoo.com> - 2011-04-16 07:43 -0700

csiph-web