Complexity of problems on graphs represented as OBDDs

To analyze the complexity of decision problems on graphs, one normally assu mes that the input size is polynomial in the number of vertices. Galperin a nd Wigderson [GW83] and, later, Papadimitriou and Yannakakis [PY86] investi gated the complexity of these problems when the input graph is represented by a polylogarithmically succinct circuit. They showed that, under such a r epresentation, certain trivial problems become intractable and that, in gen eral, there is an exponential blowup in problem complexity. Later, Balcazar , Lozano, and Toran [Bal96, BL89, BLT92, Tor88] extended these results to p roblems whose inputs are structures other than graphs. In this paper, we show that, when the input graph is represented by an orde red binary decision diagram (OBDD), there is an exponential blowup in the c omplexity of most graph problems. In particular, we show that the GAP and A GAP problems become complete for PSPACE and EXP, respectively, when the gra phs are succinctly represented by OBDDs.