Abstract
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 ∈ [n] , the set Ei of edges connecting vertices along dimension i can be decomposed into equivalence classes (so-called phases), such that flipping the direction of any S ⊆ Ei 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 · 3n) time, significantly improving upon the previously known O(n · 4n) 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 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.