MINIMUM FEEDBACK ARC SETS IN ROTATOR AND INCOMPLETE ROTATOR GRAPHS
Chi-Jung Kuo, Chiun‐Chieh Hsu, Hon-Ren Lin, Da‐Ren Chen · International Journal of Foundations of Computer Science · 2012
A feedback vertex/arc set (abbreviated as FVS/FAS) of a graph is a subset of the vertices/arcs which contains at least one vertex/arc for every cycle of that graph. A minimum FVS/FAS is an FVS/FAS which contains the smallest number of vertices/arcs. Hsu et al. [11] first proposed an algorithm which can find a minimum FVS in a rotator graph. In this paper, we present a formula for finding an FAS for a rotator graph and prove that the FAS is minimum. This formula can be easily implemented by an efficient algorithm which obtains a minimum FAS in a rotator graph. Finally, we also present a concise formula for finding a minimum FAS in an incomplete rotator graph in this paper.