{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T09:40:05Z","timestamp":1748857205738,"version":"3.41.0"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,4,25]],"date-time":"2025-04-25T00:00:00Z","timestamp":1745539200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,4,25]],"date-time":"2025-04-25T00:00:00Z","timestamp":1745539200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["GRK 2434"],"award-info":[{"award-number":["GRK 2434"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["204320"],"award-info":[{"award-number":["204320"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>A <jats:italic>unique sink orientation<\/jats:italic> (USO) is an orientation of the <jats:italic>n<\/jats:italic>-dimensional hypercube graph such that every non-empty face contains a unique sink. We consider the only known connected <jats:italic>flip graph<\/jats:italic> on USOs. This flip graph is based on the following theorem due to Schurr: given any <jats:italic>n<\/jats:italic>-dimensional USO and any one dimension\u00a0<jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$i\\in [n]$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>i<\/mml:mi>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:mo>[<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>]<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, the set <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$E_i$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>E<\/mml:mi>\n                    <mml:mi>i<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> of edges connecting vertices along dimension <jats:italic>i<\/jats:italic> can be decomposed into equivalence classes (so-called <jats:italic>phases<\/jats:italic>), such that flipping the direction of any <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$S\\subseteq E_i$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>S<\/mml:mi>\n                    <mml:mo>\u2286<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>E<\/mml:mi>\n                      <mml:mi>i<\/mml:mi>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> yields another USO if and only if <jats:italic>S<\/jats:italic> is the union of some of these phases. In this paper we provide an algorithm to compute the phases of a given USO in <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O(n\\cdot 3^n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>\u00b7<\/mml:mo>\n                    <mml:msup>\n                      <mml:mn>3<\/mml:mn>\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> time, significantly improving upon the previously known <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O(n\\cdot 4^n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>\u00b7<\/mml:mo>\n                    <mml:msup>\n                      <mml:mn>4<\/mml:mn>\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> trivial algorithm. We also show that the phase containing a given edge can be flipped using only <jats:italic>poly<\/jats:italic>(<jats:italic>n<\/jats:italic>) space additional to the space required to store the USO. We contrast this by showing that given a boolean circuit of size <jats:italic>poly<\/jats:italic>(<jats:italic>n<\/jats:italic>) succinctly encoding an <jats:italic>n<\/jats:italic>-dimensional USO, it is <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\textsf{PSPACE}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>PSPACE<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>-complete to determine whether two given edges are in the same phase. Finally, we also prove some new results on the structure of phases.<\/jats:p>","DOI":"10.1007\/s00373-025-02929-2","type":"journal-article","created":{"date-parts":[[2025,4,25]],"date-time":"2025-04-25T17:41:31Z","timestamp":1745602891000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Flipping Edge Sets in Unique Sink Orientations"],"prefix":"10.1007","volume":"41","author":[{"given":"Michaela","family":"Borzechowski","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1901-3621","authenticated-orcid":false,"given":"Simon","family":"Weber","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,4,25]]},"reference":[{"issue":"1","key":"2929_CR1","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0166-218X(95)00026-N","volume":"65","author":"D Avis","year":"1996","unstructured":"Avis, D., Fukuda, K.: Reverse search for enumeration. Discrete Appl. Math. 65(1), 21\u201346 (1996). https:\/\/doi.org\/10.1016\/0166-218X(95)00026-N. (First International Colloquium on Graphs and Optimization.)","journal-title":"Discrete Appl. Math."},{"key":"2929_CR2","doi-asserted-by":"publisher","unstructured":"Borzechowski, M., Doolittle, J., Weber, S.: A universal construction for unique sink orientations (2022). https:\/\/doi.org\/10.48550\/ARXIV.2211.06072","DOI":"10.48550\/ARXIV.2211.06072"},{"key":"2929_CR3","doi-asserted-by":"publisher","unstructured":"Borzechowski, M., Weber, S.: On degeneracy in the P-matroid oriented matroid complementarity problem. In: Abstracts of the 39th European Workshop on Computational Geometry (EuroCG \u201923), 9(1)\u20139(7) (2023). https:\/\/doi.org\/10.48550\/ARXIV.2302.14585","DOI":"10.48550\/ARXIV.2302.14585"},{"key":"2929_CR4","doi-asserted-by":"publisher","unstructured":"Bosshard, V., G\u00e4rtner, B.: Pseudo unique sink orientations (2017). https:\/\/doi.org\/10.48550\/ARXIV.1704.08481","DOI":"10.48550\/ARXIV.1704.08481"},{"key":"2929_CR5","unstructured":"Dorfman, D.: Personal communication (2022)"},{"issue":"4\u20135","key":"2929_CR6","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1142\/S0218195904001500","volume":"14","author":"K Fischer","year":"2004","unstructured":"Fischer, K., G\u00e4rtner, B.: The smallest enclosing ball of balls: combinatorial structure and algorithms. IJCGA 14(4\u20135), 341\u2013387 (2004). https:\/\/doi.org\/10.1142\/S0218195904001500","journal-title":"IJCGA"},{"issue":"2","key":"2929_CR7","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/s00454-009-9182-2","volume":"42","author":"J Foniok","year":"2009","unstructured":"Foniok, J., Fukuda, K., G\u00e4rtner, B., L\u00fcthi, H.-J.: Pivoting in linear complementarity: two polynomial-time cases. Discrete Comput. Geom. 42(2), 187\u2013205 (2009). https:\/\/doi.org\/10.1007\/s00454-009-9182-2","journal-title":"Discrete Comput. Geom."},{"key":"2929_CR8","doi-asserted-by":"publisher","unstructured":"G\u00e4rtner, B., R\u00fcst, L.: Simple stochastic games and P-matrix generalized linear complementarity problems. In: Maciej, L., R\u00fcdiger, R., (eds), Fundamentals of Computation Theory, pages 209\u2013220, Springer, Berlin (2005). https:\/\/doi.org\/10.1007\/11537311_19","DOI":"10.1007\/11537311_19"},{"key":"2929_CR9","doi-asserted-by":"publisher","unstructured":"G\u00e4rtner, B., Schurr, I.: Linear programming and unique sink orientations. In: Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 749\u2013757 (2006). https:\/\/doi.org\/10.5555\/1109557.1109639","DOI":"10.5555\/1109557.1109639"},{"key":"2929_CR10","doi-asserted-by":"publisher","unstructured":"G\u00e4rtner, B., Thomas, A.: The complexity of recognizing unique sink orientations. In Ernst\u00a0W. Mayr and Nicolas Ollinger, editors, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), volume\u00a030 of Leibniz International Proceedings in Informatics (LIPIcs), pages 341\u2013353, Dagstuhl, Germany, (2015). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik. https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2015.341","DOI":"10.4230\/LIPIcs.STACS.2015.341"},{"issue":"5","key":"2929_CR11","doi-asserted-by":"publisher","first-page":"1018","DOI":"10.1137\/S0097539793250287","volume":"24","author":"B G\u00e4rtner","year":"1995","unstructured":"G\u00e4rtner, B.: A subexponential algorithm for abstract optimization problems. SIAM J. Comput. 24(5), 1018\u20131035 (1995). https:\/\/doi.org\/10.1137\/S0097539793250287","journal-title":"SIAM J. Comput."},{"issue":"1","key":"2929_CR12","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s00453-007-0175-3","volume":"49","author":"N Halman","year":"2007","unstructured":"Halman, N.: Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems. Algorithmica 49(1), 37\u201350 (2007). https:\/\/doi.org\/10.1007\/s00453-007-0175-3","journal-title":"Algorithmica"},{"key":"2929_CR13","doi-asserted-by":"publisher","first-page":"2255","DOI":"10.1090\/tran\/8199","volume":"375","author":"E Hartung","year":"2022","unstructured":"Hartung, E., Hoang, H.P., M\u00fctze, T., Williams, A.: Combinatorial generation via permutation languages. I. Fund. Trans. Am. Math. Soc. 375, 2255\u20132291 (2022). https:\/\/doi.org\/10.1090\/tran\/8199","journal-title":"Fund. Trans. Am. Math. Soc."},{"issue":"2","key":"2929_CR14","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1090\/S0273-0979-1992-00318-X","volume":"27","author":"JC Lagarias","year":"1992","unstructured":"Lagarias, J.C., Shor, P.W.: Keller\u2019s cube-tiling conjecture is false in high dimensions. Bull. Am. Math. Soc. 27(2), 279\u2013283 (1992). https:\/\/doi.org\/10.1090\/S0273-0979-1992-00318-X","journal-title":"Bull. Am. Math. Soc."},{"issue":"1","key":"2929_CR15","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s00493-006-0007-0","volume":"26","author":"J Matou\u0161ek","year":"2006","unstructured":"Matou\u0161ek, J.: The number of unique-sink orientations of the hypercube. Combinatorica 26(1), 91\u201399 (2006). https:\/\/doi.org\/10.1007\/s00493-006-0007-0","journal-title":"Combinatorica"},{"key":"2929_CR16","doi-asserted-by":"publisher","unstructured":"Nishimura, N.: Introduction to reconfiguration. Algorithms, 11(4) (2018). https:\/\/doi.org\/10.3390\/a11040052","DOI":"10.3390\/a11040052"},{"issue":"2","key":"2929_CR17","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"WJ Savitch","year":"1970","unstructured":"Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4(2), 177\u2013192 (1970). https:\/\/doi.org\/10.1016\/S0022-0000(70)80006-X","journal-title":"J. Comput. Syst. Sci."},{"key":"2929_CR18","doi-asserted-by":"publisher","unstructured":"Schurr, I.: Unique Sink Orientations of Cubes. PhD thesis, ETH Z\u00fcrich (2004). https:\/\/doi.org\/10.3929\/ethz-a-004844278","DOI":"10.3929\/ethz-a-004844278"},{"issue":"4","key":"2929_CR19","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1007\/s00454-003-0813-8","volume":"31","author":"I Schurr","year":"2004","unstructured":"Schurr, I., Szab\u00f3, T.: Finding the sink takes some time: an almost quadratic lower bound for finding the sink of unique sink oriented cubes. Discrete Comput. Geom. 31(4), 627\u2013642 (2004). https:\/\/doi.org\/10.1007\/s00454-003-0813-8","journal-title":"Discrete Comput. Geom."},{"key":"2929_CR20","doi-asserted-by":"crossref","unstructured":"Stickney, A., Watson, L.: Digraph models of Bard-type algorithms for the linear complementarity problem. Math. Oper. Res. 3(4), 322\u2013333 (1978). https:\/\/www.jstor.org\/stable\/3689630","DOI":"10.1287\/moor.3.4.322"},{"key":"2929_CR21","doi-asserted-by":"publisher","unstructured":"Szab\u00f3, T., Welzl, E.: Unique sink orientations of cubes. In: Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on, pp. 547\u2013555. IEEE (2001). https:\/\/doi.org\/10.1109\/SFCS.2001.959931","DOI":"10.1109\/SFCS.2001.959931"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02929-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-025-02929-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02929-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T09:15:41Z","timestamp":1748855741000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-025-02929-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,25]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["2929"],"URL":"https:\/\/doi.org\/10.1007\/s00373-025-02929-2","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2025,4,25]]},"assertion":[{"value":"10 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"64"}}