The complexity of connectivity problems on context-free graph languages

摘要

In a very general frame, we analyze the complexity of connectivity problems on sets of graphs defined by context-free graph rewriting systems under various restrictions. In particular, we show the following results: If L is the set of all context-free graph rewriting systems that define at least one disconnected graph (connected graph, respectively), then L is DEXPTIME-complete. For linear systems or systems that define only finite sets of graphs, L is PSPACE-complete. For linear systems that define finite sets of graphs, L is NP-complete. For deterministic systems the complexity class of L depends on the used graph grammar model. L is P-complete for simple context-free graph rewriting systems as for example hyperedge replacement systems, but NP-complete (co-NP-complete, respectively), for boundary node label controlled graph grammars and more powerful systems.