### 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 language | English (US) |
---|---|

Title of host publication | STACS 98 - 15th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings |

Pages | 216-226 |

Number of pages | 11 |

DOIs | |

State | Published - Dec 1 1998 |

Externally published | Yes |

Event | 15th Annual Symposium on Theoretical Aspects of Computer Science, STACS 98 - Paris, France Duration: Feb 25 1998 → Feb 27 1998 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 1373 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 15th Annual Symposium on Theoretical Aspects of Computer Science, STACS 98 |
---|---|

Country | France |

City | Paris |

Period | 2/25/98 → 2/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

*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