On Flipping Edge Sets in Unique Sink Orientations

A <i>unique sink orientation</i> (USO) is an orientation of the <i>n</i>-dimensional hypercube graph such that every non-empty face contains a unique sink. We consider the only known connected <i>flip graph</i> on USOs. This flip graph is based on the following theorem due to Schurr: given any <i>n</i>-dimensional USO and any one dimension <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>i</mml:mi> <mml:mo>∈</mml:mo> <mml:mo>[</mml:mo> <mml:mi>n</mml:mi> <mml:mo>]</mml:mo></mml:mrow> </mml:math> , the set <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>E</mml:mi> <mml:mi>i</mml:mi></mml:msub> </mml:math> of edges connecting vertices along dimension <i>i</i> can be decomposed into equivalence classes (so-called <i>phases</i>), such that flipping the direction of any <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>S</mml:mi> <mml:mo>⊆</mml:mo> <mml:msub><mml:mi>E</mml:mi> <mml:mi>i</mml:mi></mml:msub> </mml:mrow> </mml:math> yields another USO if and only if <i>S</i> is the union of some of these phases. In this paper we provide an algorithm to compute the phases of a given USO in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>·</mml:mo> <mml:msup><mml:mn>3</mml:mn> <mml:mi>n</mml:mi></mml:msup> <mml:mo>)</mml:mo></mml:mrow> </mml:math> time, significantly improving upon the previously known <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>·</mml:mo> <mml:msup><mml:mn>4</mml:mn> <mml:mi>n</mml:mi></mml:msup> <mml:mo>)</mml:mo></mml:mrow> </mml:math> trivial algorithm. We also show that the phase containing a given edge can be flipped using only <i>poly</i>(<i>n</i>) space additional to the space required to store the USO. We contrast this by showing that given a boolean circuit of size <i>poly</i>(<i>n</i>) succinctly encoding an <i>n</i>-dimensional USO, it is <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>PSPACE</mml:mi></mml:math> -complete to determine whether two given edges are in the same phase. Finally, we also prove some new results on the structure of phases.