Published by MIT Press. Copyright 1999 Massachusetts Institute of Technology.

Your institution may already be a subscriber to CJTCS. If not, please subscribe.

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 and, later, Papadimitriou and Yannakakis 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 blowup in problem complexity. Later, Balcazar, Lozano, and Toran extended these results to problems whose inputs are structures other than graphs.

In this paper, we show that, when the input graph is represented by an ordered binary decision diagram (OBDD), there is an exponential blowup 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.

• Preformatted versions of the article
  • DVI (82,460 bytes)
  • PostScript ( 378,624 bytes)
  • PDF (340,523 bytes)
  • Audio by AsTeR (to appear)
• Source materials for custom formatting
  • LaTeX (cj99-05.tex, 56,936 bytes)
  • BIBTeX (cj99-05.bib, 8,816 bytes)
  • Parameter settings for custom formatting (cjropts.tex, 165 bytes)
  • Self citation in BIBTeX (324 bytes)
• Online discussion
• Instructions for Readers

DOI: 10.4086/cjtcs.1999.005

---

Article 4 Article 6
Volume 1999 Published articles

Last modified: Sat Mar 20 09:32:31 CST 1999