<p>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.</p>

<p>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. </p>

CC BY-SA 3.0
2018-03-26T08:51:04.223Z
It might be helpful if you added the definition of a bipolar orientation.
tranisstor
CC BY-SA 3.0
2018-03-26T08:54:06.600Z
@tranisstor done.
seteropere
<graph-theory><graph-algorithms><directed-acyclic-graph>
Realization of a bipolar orientation by a mixed graph
seteropere
# Realization of a bipolar orientation by a mixed graph

(Asked by: username_0 on 2014-12-23)

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.

**Tags:** graph-theory, graph-algorithms, directed-acyclic-graph
> **Comments:**
> **username_1**: It might be helpful if you added the definition of a bipolar orientation.  
> **username_0**: @tranisstor done.  

---

## 0 answers

