Feedback Arc Set in Oriented Graphs
Indra Rajasingh, Bharati Rajan, Little Joice · 2009
A feedback arc set in a directed graph D is a set S of arcs in D such that D\ S is acyclic. The problem of determining a feedback arc set with least number of arcs is NP - complete for a general digraph. We define the strong feedback arc number ßs(G) for various orientations of an undirected graph G. The strong feedback arc problem of an undirected graph is to find a strong feedback arc set S of G(O) for some strongly oriented O(G) such that |S|=ßs(G) . In this paper our focus is on interconnection networks with ßs=1.