Complexity of problems on graphs represented as OBDDs (extended abstract)

J. Feigenbaum, S. Kannan, M. Y. Vardi, M. Viswanathan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

To analyze the complexity of decision problems on graphs, one normally assumes that the input size is polynomial in the number of vertices. Galperin and Wigderson [13] and, later, Papadimitriou and Yannakakis [18] investigated the complexity of these problems when the input graph is represented by a polylogarithmically succinct circuit. They showed that, under such a representation, certain trivial problems become intractable and that, in general, there is an exponential blow up in problem complexity. In this paper, we show that, when the input graph is represented by a small ordered binary decision diagram (OBDD), there is an exponential blow up in the complexity of most graph problems. In particular, we show that the GAP and AGAP problems become complete for PSPACE and EXP, respectively, when the graphs are succinctly represented by OBDDs.

Original languageEnglish (US)
Title of host publicationSTACS 98 - 15th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
Pages216-226
Number of pages11
DOIs
StatePublished - Dec 1 1998
Externally publishedYes
Event15th Annual Symposium on Theoretical Aspects of Computer Science, STACS 98 - Paris, France
Duration: Feb 25 1998Feb 27 1998

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1373 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other15th Annual Symposium on Theoretical Aspects of Computer Science, STACS 98
CountryFrance
CityParis
Period2/25/982/27/98

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Complexity of problems on graphs represented as OBDDs (extended abstract)'. Together they form a unique fingerprint.

  • Cite this

    Feigenbaum, J., Kannan, S., Vardi, M. Y., & Viswanathan, M. (1998). Complexity of problems on graphs represented as OBDDs (extended abstract). In STACS 98 - 15th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings (pp. 216-226). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1373 LNCS). https://doi.org/10.1007/BFb0028563