An orientation of a simple undirected graph $G=(V,E)$ is a directed graph $G' = (V,E')$ that is constructed by including either $(u,v) \in E'$ or $(v,u) \in E'$, but not both, for all $(u,v) \in E$. Let $d_{G'}$ be the shortest path distance in $G'$. My question: Given a $G$, does there exist a polynomial-time algorithm that finds an orientation such that $d_{G'}(u,v) \geq 3$, for any pair of vertices $u \neq v$ that are part of some (unspecified) Maximum Ind. Set (MIS) of $G$? --- Note 1: It's not possible to find such an orientation that satisfies this for *every* MIS simultaneously. Take a cycle of length 5. Every possible orientation has a length-two path, and the two endpoints of this path are a MIS. Note 2: Of course there always exists such an orientation. Since if we know an MIS in $G$, we can simply orient all edges as incoming edges for every $u$ in that MIS. In this case, we have the stronger result $d_{G'}(u,v) = +\infty$.