igraph (version 1.3.5)

feedback_arc_set: Finding a feedback arc set in a graph

Description

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

Usage

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

Value

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

Arguments

graph

The input graph

weights

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.

algo

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”.

Details

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).

References

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

Examples

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