The Complexity of Problems on Graphs Represented as OBDDs
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.