Chicago Journal of Theoretical Computer Science

Volume 1999

Article 5

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

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

The Complexity of Problems on Graphs Represented as OBDDs

Joan Feigenbaum (AT&T Labs Reesearch), Sampath Kannan (University of Pennsylvania), Moshe Y. Vardi (Rice University), and Mahesh Viswanathan (University of Pennsylvania)
6 August 1999

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.

DOI: 10.4086/cjtcs.1999.005
[] Article 4 [] Article 6
[back] Volume 1999 [back] Published articles
[CJCTS home]

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