[Bioc-devel] graph: maximum acyclic subgraph / minimum feedback edge set

[Ludwig Geistlinger]

Hi,

I would like to transform a directed graph with cycles, e.g. a gene
regulatory network, into a DAG. In particular, I would like to do that by
removing a minimal set of edges.

This problem is known to be NP-hard

https://en.wikipedia.org/wiki/Feedback_arc_set

but, apparently, several approximation algorithms for the problem have
been developed.

However, when screening e.g. through the manuals of the graph, igraph, and
ggm packages, I do not find functionality for that.

I wonder, whether developers on the mailing list, dealing with graphs and
networks, can point me to an R implementation of the desired
functionality?

Thx & Best,
Ludwig


-- 
Dipl.-Bioinf. Ludwig Geistlinger

Lehr- und Forschungseinheit für Bioinformatik
Institut für Informatik
Ludwig-Maximilians-Universität München
Amalienstrasse 17, 2. Stock, Büro A201
80333 München

Tel.: 089-2180-4067
eMail: Ludwig.Geistlinger at bio.ifi.lmu.de