Complexity of decision problems for hyperedge replacement grammars

Abstract

This paper investigates complexity of various decision problems for hyperedge replacement grammars, starting with the uniform membership problem. It turns out that the complexity of the latter problem depends on how one defines a hypergraph. There are two commonly used definitions in the field, which differ in whether repetitions of attachment nodes of a hyperedge are allowed in a hypergraph or not. We show that, for arbitrary grammars, the problem under consideration is EXPTIME-complete, even for string-generating hyperedge replacement grammars, but it is NP-complete if repetitions are not allowed. We extend the developed proof techniques in order to prove a general EXPTIME-hardness result that covers a lot of decision problems concerning hyperedge replacement grammars. In particular, checking whether a grammar generates some graph satisfying a property that cannot be recovered from its multiset of hyperedge labels is EXPTIME-hard. We call such properties non-Parikh. They include such well-known graph-theoretic properties as e.g.~connectedness, Eulerianity, Hamiltonianity, acyclicity. A tight upper bound is established for EXPTIME-compatible properties via the Filter Theorem.

arXiv commentContent is extended substantially as compared to the previous version (new meta-theorems are included here), and presentation is improved significantly