Changes
<onlyinclude>
Can we determine in polynomial time the maximum size of a [[SourceSink-stable set|source-sink reorientable set]] in an acyclic digraph? Is it true that it always equals the maximum size of the union of two [[SourceSink-stable set|sourcesink-stable sets]]?
</onlyinclude>
==Remarks==
By a result of Sebő Erdős, Frank, and Kun <refname="ErFrKu"/>A. (that can also be derived from Sebő, ''Minmax relations for cyclically ordered digraphs'', Journal of Combinatorial Theory, Series B 97 (2007), 518-552. [http://dx.doi.org/10.1016/j.jctb.2006.09.005 DOI link].<ref name="Sebo"/ref>), the maximum size of the union of two [[SourceSink-stable set|sourcesink-stable sets]] can be computed in polynomial time, so the validity of the characterization would imply a polynomial algorithm.
The following simple example shows that the union of two sourcesink-stable sets (''u'' and ''v'' in the example) may not be [[SourceSink-stable set|source-sink reorientable]].
[[File:Fries.png]]
==References==
<references>
<ref name="ErFrKu">D. Erdős, A. Frank, K. Kun, ''Sink-stable sets of digraphs'', [http://www.cs.elte.hu/egres/tr/egres-11-06.pdf Egres Technical Report no. 2011-06], [http://arxiv.org/abs/1205.6071 arXiv link].</ref>
<ref name="Sebo">A. Sebő, ''Minmax relations for cyclically ordered digraphs'', Journal of Combinatorial Theory, Series B 97 (2007), 518-552. [http://dx.doi.org/10.1016/j.jctb.2006.09.005 DOI link].</ref>
<references/>
