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
