# Maximum size of a source-sink reorientable set

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?

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.

## References

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