Document Open Access Logo

The Complexity of Recognizing Unique Sink Orientations

Authors Bernd Gärtner, Antonis Thomas

PDF
Thumbnail PDF

File

LIPIcs.STACS.2015.341.pdf
  • Filesize: 0.67 MB
  • 13 pages

Document Identifiers

Author Details

Bernd Gärtner
Antonis Thomas

Cite As Get BibTex

Bernd Gärtner and Antonis Thomas. The Complexity of Recognizing Unique Sink Orientations. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 341-353, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.STACS.2015.341

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.

Subject Classification

Keywords
  • complexity
  • recognizing
  • unique sink orientations
  • coNP
  • PSPACE

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. José L. Balcázar, Antoni Lozano, and Jacobo Torán. The complexity of algorithmic problems on succinct instances. In Ricardo Baeza-Yates and Udi Manber, editors, Computer Science, pages 351-377. Springer US, 1992. Google Scholar
  2. Gregory E. Coxson. The P-matrix problem is co-NP-complete. Mathematical Programming, 64(1-3):173-178, 1994. Google Scholar
  3. Kaspar Fischer and Bernd Gärtner. The smallest enclosing ball of balls: combinatorial structure and algorithms. Internat. J. Comput. Geom. Appl., 14(4-5):341-378, 2004. Google Scholar
  4. Jan Foniok, Bernd Gärtner, Lorenz Klaus, and Markus Sprecher. Counting Unique-Sink Orientations. Discrete Applied Mathematics, 163, Part 2:155-164, 2014. Google Scholar
  5. Hana Galperin and Avi Wigderson. Succinct representations of graphs. Information and Control, 56(3):183-198, 1983. Google Scholar
  6. Bernd Gärtner. The Random-Facet simplex algorithm on combinatorial cubes. Random Structures & Algorithms, 20(3):353-381, 2002. Google Scholar
  7. Bernd Gärtner and Leo Rüst. Simple stochastic games and P-matrix generalized linear complementarity problems. In Maciej Liskiewicz and Rüdiger Reischuk, editors, Proceedings of the 15th International Symposium on Fundamentals of Computation Theory (FCT'05), volume 3623 of Lecture Notes in Computer Science, pages 209-220. Springer, 2005. Google Scholar
  8. Bernd Gärtner and Ingo Schurr. Linear Programming and Unique Sink Orientations. In Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 749-757, 2006. Google Scholar
  9. Peter L. Hammer, Bruno Simeone, Thomas M. Liebling, and Dominique de Werra. From linear separability to unimodality: A hierarchy of pseudo-Boolean functions. SIAM J. Discrete Math., 1(2):174-184, 1988. Google Scholar
  10. Richard E. Ladner. The circuit value problem is log space complete for P. SIGACT News, 7(1):18-20, 1975. Google Scholar
  11. Nancy Lynch. Log space recognition and translation of parenthesis languages. J. ACM, 24(4):583-590, 1977. Google Scholar
  12. Jiří Matoušek. The number of Unique-Sink Orientations of the hypercube*. Combinatorica, 26(1):91-99, 2006. Google Scholar
  13. Christos H. Papadimitriou and Mihalis Yannakakis. A note on succinct representations of graphs. Information and Control, 71(3):181-185, 1986. Google Scholar
  14. Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci., 4(2):177-192, 1970. Google Scholar
  15. Ingo Schurr and Tibor Szabó. Finding the sink takes some time: An almost quadratic lower bound for finding the sink of unique sink oriented cubes. Discrete & Computational Geometry, 31(4):627-642, 2004. Google Scholar
  16. Alan Stickney and Layne Watson. Digraph models of Bard-type algorithms for the linear complementarity problem. Math. Oper. Res., 3(4):322-333, 1978. Google Scholar
  17. Tibor Szabó and Emo Welzl. Unique Sink Orientations of cubes. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS'01), pages 547-555, 2001. Google Scholar
  18. Stefano Tessaro. Randomized algorithms to locate the sink in low dimensional Unique Sink Orientations of cubes. Semester thesis, Computer Science Department, ETH Zürich, 2004. Google Scholar
  19. Kathy Williamson-Hoke. Completely unimodal numberings of a simple polytope. Discrete Applied Mathematics, 20(1):69-81, 1988. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact