feedback_arc_set {igraph}R Documentation

Finding a feedback arc set in a graph


A feedback arc set of a graph is a subset of edges whose removal breaks all cycles in the graph.


feedback_arc_set(graph, weights = NULL, algo = c("approx_eades", "exact_ip"))



The input graph


Potential edge weights. If the graph has an edge attribute called ‘weight’, and this argument is NULL, then the edge attribute is used automatically. The goal of the feedback arc set problem is to find a feedback arc set with the smallest total weight.


Specifies the algorithm to use. “exact_ip” solves the feedback arc set problem with an exact integer programming algorithm that guarantees that the total weight of the removed edges is as small as possible. “approx_eades” uses a fast (linear-time) approximation algorithm from Eades, Lin and Smyth. “exact” is an alias to “exact_ip” while “approx” is an alias to “approx_eades”.


Feedback arc sets are typically used in directed graphs. The removal of a feedback arc set of a directed graph ensures that the remaining graph is a directed acyclic graph (DAG). For undirected graphs, the removal of a feedback arc set ensures that the remaining graph is a forest (i.e. every connected component is a tree).


An edge sequence (by default, but see the option of igraph_options) containing the feedback arc set.


Peter Eades, Xuemin Lin and W.F.Smyth: A fast and effective heuristic for the feedback arc set problem. Information Processing Letters 47:6, pp. 319-323, 1993


g <- sample_gnm(20, 40, directed=TRUE)
feedback_arc_set(g, algo="approx")

[Package igraph version 1.3.5 Index]