Cyclic stable set

From Egres Open
Jump to: navigation, search

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].


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