A unique sink orientation (USO) is an orientation of the n-dimensional hypercube graph such that every non-empty face contains a unique sink. We consider the only known connected flip graph on USOs. This flip graph is based on the following theorem due to Schurr: given any n-dimensional USO and any one dimension \(i\in [n]\) , the set \(E_i\) of edges connecting vertices along dimension i can be decomposed into equivalence classes (so-called phases), such that flipping the direction of any \(S\subseteq E_i\) yields another USO if and only if S is the union of some of these phases. In this paper we provide an algorithm to compute the phases of a given USO in \(O(n\cdot 3^n)\) time, significantly improving upon the previously known \(O(n\cdot 4^n)\) trivial algorithm. We also show that the phase containing a given edge can be flipped using only poly(n) space additional to the space required to store the USO. We contrast this by showing that given a boolean circuit of size poly(n) succinctly encoding an n-dimensional USO, it is \(\textsf{PSPACE}\) -complete to determine whether two given edges are in the same phase. Finally, we also prove some new results on the structure of phases.
