License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.341
URN: urn:nbn:de:0030-drops-49252
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4925/
Gärtner, Bernd ;
Thomas, Antonis
The Complexity of Recognizing Unique Sink Orientations
Abstract
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.
BibTeX - Entry
@InProceedings{grtner_et_al:LIPIcs:2015:4925,
author = {Bernd G{\"a}rtner and Antonis Thomas},
title = {{The Complexity of Recognizing Unique Sink Orientations}},
booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
pages = {341--353},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-78-1},
ISSN = {1868-8969},
year = {2015},
volume = {30},
editor = {Ernst W. Mayr and Nicolas Ollinger},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/4925},
URN = {urn:nbn:de:0030-drops-49252},
doi = {10.4230/LIPIcs.STACS.2015.341},
annote = {Keywords: complexity, recognizing, unique sink orientations, coNP, PSPACE}
}
Keywords: |
|
complexity, recognizing, unique sink orientations, coNP, PSPACE |
Collection: |
|
32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) |
Issue Date: |
|
2015 |
Date of publication: |
|
26.02.2015 |