On Flipping Edge Sets in Unique Sink Orientations

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 Eiof edges connecting vertices along dimension i can be decomposed into equivalence classes (so-called phases ), such that flipping the direction of any S⊆Eiyields 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.