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"))`

## 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`

”.

## Value

An edge sequence (by default, but see the `return.vs.es`

option
of `igraph_options()`

) containing the feedback arc set.

## 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

## See also

Other structural.properties:
`bfs()`

,
`component_distribution()`

,
`connect()`

,
`constraint()`

,
`coreness()`

,
`degree()`

,
`dfs()`

,
`distance_table()`

,
`edge_density()`

,
`girth()`

,
`is_acyclic()`

,
`is_dag()`

,
`is_matching()`

,
`k_shortest_paths()`

,
`knn()`

,
`reciprocity()`

,
`subcomponent()`

,
`subgraph()`

,
`topo_sort()`

,
`transitivity()`

,
`unfold_tree()`

,
`which_multiple()`

,
`which_mutual()`

Graph cycles
`girth()`

,
`has_eulerian_path()`

,
`is_acyclic()`

,
`is_dag()`

## Examples

```
g <- sample_gnm(20, 40, directed = TRUE)
feedback_arc_set(g)
#> + 6/40 edges from 7eeadb7:
#> [1] 6->15 6->19 9->15 11-> 3 16->10 17-> 5
feedback_arc_set(g, algo = "approx_eades")
#> + 6/40 edges from 7eeadb7:
#> [1] 6->15 6->19 9->15 11-> 3 16->10 17-> 5
```