# Cyclic stable set

Cyclic stable sets with respect to a coherent cyclic order were defined by Bessy and Thomassé ^{[1]}.

Let *D=(V,A)* be a strongly connected directed graph. We introduce the following notions:

- A
**cyclic order**is a cyclic order of*V*. - An
**elementary operation**on a cyclic order is the interchange of two consecutive non-adjacent nodes. - Two cyclic orders are
**equivalent**if one can be obtained from the other by a sequence of elementary operations. - An
**opening**of a cyclic order is a linear order obtained from it. - A
**forward arc**(backward arc) of an opening of a cyclic order is an arc whose tail is smaller (larger) in the order than its head.

Given a cyclic order *<* and a directed cycle *C*, the number of backward arcs in *C* is the same in any opening of *<*. Moreover it is the same in any opening of any equivalent cyclic order. This number is called the index of *C* with respect to *<*. A cyclic order is called **coherent** if every arc is in a directed cycle of index 1. It follows that coherence is a property of equivalence classes of cyclic orders. Bessy and Thomassé proved that every strong digraph has a coherent cyclic order.

A stable set *S* of *D* is a **cyclic stable set** with respect to a coherent cyclic order *<* if there is an equivalent cyclic order where the nodes of *S* form an interval. It follows from the above that a node set *S* is a cyclic stable set if and only if [math]|S \cap V(C)|[/math] is at most the index of *C* for any directed cycle *C*.

For more details, see Sebő ^{[2]}, and Charbit and Sebő ^{[3]}. An *O(nm)* algorithm for finding a coherent cyclic order was given by Iwata and Matsuda ^{[4]}.

## References

- ↑ S. Bessy, S. Thomassé,
*Spanning a strong digraph by α circuits: A proof of Gallai’s conjecture*, DOI link, author link - ↑ A. Sebő,
*Minmax relations for cyclically ordered digraphs*, DOI link, author link - ↑ P. Charbit, A. Sebő,
*Cyclic orders: Equivalence and duality*, DOI link, author link - ↑ S. Iwata, T. Matsuda,
*Finding coherent cyclic orders in strong digraphs*, DOI link