# Realization of a bipolar orientation by a mixed graph

Given an undirected graph $G(V,E)$ and a bipolar orientation $s$ over $G$, consider the problem of identifying $s$ by finding the minimum number of edges such that when orienting them in a particular way they give arise only to $s$ as bipolar orientation. An orientation $s$ for a graph $G$ is bipolar if $s$ is acyclic and has a single source and single sink.

That is, find the minimum subset of edges $\hat{E}\subseteq E$ such that if we orient them $\vec{E}$, the only bipolar orientation for the mixed graph $(V,E-\hat{E},\vec{E})$ is $s$. Is this problem known? has been tackled before? Any pointer is appreciated.

• It might be helpful if you added the definition of a bipolar orientation. – tranisstor Mar 26 '18 at 8:51
• @tranisstor done. – seteropere Mar 26 '18 at 8:54