Maximum size of a source-sink reorientable set

From Egres Open
Jump to: navigation, search

Can we determine in polynomial time the maximum size of a source-sink reorientable set in an acyclic digraph? Is it true that it always equals the maximum size of the union of two sink-stable sets?


Solved b.jpg

If we replace u and v by larger stable sets in the example below, then we obtain an instance where the union of two sink-stable sets is larger than the maximum size of a source-sink reorientable set. Erika Bérczi-Kovács showed that the latter can be computed in polynomial time using minimum cost circulations.

Remarks

By a result of Erdős, Frank, and Kun [1] (that can also be derived from Sebő [2]), the maximum size of the union of two sink-stable sets can be computed in polynomial time, so the validity of the characterization would imply a polynomial algorithm for determining the size (but not necessarily for finding a largest source-sink reorientable set).

The following simple example shows that the union of two sink-stable sets (u and v in the example) may not be source-sink reorientable.

Fries.png

References

  1. D. Erdős, A. Frank, K. Kun, Sink-stable sets of digraphs, Egres Technical Report no. 2011-06, arXiv link
  2. A. Sebő, Minmax relations for cyclically ordered digraphs, Journal of Combinatorial Theory, Series B 97 (2007), 518-552. DOI link, author link