Feedback Arc Set
In graph theory, a directed graph may contain directed cycles, a one-way loop of edges. In some applications, such cycles are undesirable, and we wish to eliminate them and obtain a directed acyclic graph (DAG). One way to do this is simply to drop edges from the graph to break the cycles. A feedback arc set (FAS) or feedback edge set is a set of edges which, when removed from the graph, leave a DAG. Put another way, it's a set containing at least one edge of every cycle in the graph.
Closely related are the feedback vertex set, which is a set of vertices containing at least one vertex from every cycle in the directed graph, and the minimum spanning tree, which is the undirected variant of the feedback arc set problem.
A minimal feedback arc set (one that can not be reduced in size by removing any edges) has the additional property that, if the edges in it are reversed rather than removed, then the graph remains acyclic. Finding a small edge set with this property is a key step in layered graph drawing.
Read more about Feedback Arc Set: Example, Computational Complexity
Famous quotes containing the words arc and/or set:
“You say that you are my judge; I do not know if you are; but take good heed not to judge me ill, because you would put yourself in great peril.”
—Joan Of Arc (c.1412–1431)
“... many of the things which we deplore, the prevalence of tuberculosis, the mounting record of crime in certain sections of the country, are not due just to lack of education and to physical differences, but are due in great part to the basic fact of segregation which we have set up in this country and which warps and twists the lives not only of our Negro population, but sometimes of foreign born or even of religious groups.”
—Eleanor Roosevelt (1884–1962)