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.

  • $\begingroup$ It might be helpful if you added the definition of a bipolar orientation. $\endgroup$
    – tranisstor
    Mar 26, 2018 at 8:51
  • 1
    $\begingroup$ @tranisstor done. $\endgroup$
    – seteropere
    Mar 26, 2018 at 8:54


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.