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
