On Flipping Edge Sets in Unique Sink Orientations

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  $$ , the set $$ of edges connecting vertices along dimension i can be decomposed into equivalence classes (so-called phases), such that flipping the direction of any $$ 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 $$ time, significantly improving upon the previously known $$ 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 $$ -complete to determine whether two given edges are in the same phase. Finally, we also prove some new results on the structure of phases.