Sink-stable set

Let D=(V,A) be a directed graph. A stable set S is sink-stable if by reversing some directed cuts of D we may get a digraph where every node in S is a sink. The notion was introduced in , where it was shown that the maximum weight of the union of k sink-stable sets can be computed in polynomial time.

There is a strong relation between sink-stable sets of acyclic digraphs and cyclic stable sets defined by Bessy and Thomassé (see also Sebő ). If we denote by [math]D^*[/math] the strongly connected digraph obtained by adding a reverse arc for each arc of D, then the sink-stable sets of D are exactly the cyclic stable sets of [math]D^*[/math] with respect to the coherent cyclic order defined by a topological order of D. The argument goes as follows.

• A set S is cyclic stable if and only if there is an opening of an equivalent cyclic order where no forward arcs enter S.
• The set of forward arcs in an opening of an equivalent cyclic order is obtained from A (the original set of forward arcs) by reversing some directed cuts, because in one elementary operation (interchange of nonadjacent consecutive vertices, and opening of the cyclic order somewhere) the set of forward arcs is reversed on one directed cut.
• Conversely, if we consider the set of forward arcs, and reverse a directed cut, then the obtained arc set is the set of forward arcs in an opening of an equivalent cyclic order: we can take a topological order where the first k nodes form one side of the cut, and then open this order after the first k nodes.
• It follows that a set S is cyclic stable if and only if we can reverse some directed cuts of A so that no arc leaves S.

A (not necessarily stable) node set X of a digraph D is source-sink reorientable if there is a reorientation of D obtained by reversing some directed cuts where every node of X is either a source or a sink.