2026-07-22T05:47:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4925 2024-03-06T10:35:34Z ddc:004 open_access

The Complexity of Recognizing Unique Sink Orientations Gärtner, Bernd Thomas, Antonis complexity recognizing unique sink orientations coNP PSPACE Given a Boolean Circuit with n inputs and n outputs, we want to decide if it represents a Unique Sink Orientation (USO). USOs are useful combinatorial objects that serve as abstraction of many relevant optimization problems. We prove that recognizing a USO is coNP-complete. However, the situation appears to be more complicated for recognizing acyclic USOs. Firstly, we give a construction to prove that there exist cyclic USOs where the smallest cycle is of superpolynomial size. This implies that the straightforward representation of a cycle (i.e. by a list of vertices) does not make up for a coNP certificate. Inspired by this fact, we investigate the connection of recognizing an acyclic USO to PSPACE and we prove that the problem is PSPACE-complete. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bernd Gärtner and Antonis Thomas 2015 Is Part Of LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2015.341 urn:nbn:de:0030-drops-49252 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.341 eng https://creativecommons.org/licenses/by/3.0/legalcode