Recognising \(k\)-connected hypergraphs in cubic time (Q685463)

It is known that, in general, the recognition of (hyper)graph languages generated by hyperedge-replacement grammars is an NP-complete problem. A special case is considered that leads to an algorithm running in cubic time. We study hypergraph languages generated by hyperedge-replacement grammars or order \(k\), where order \(k\) means that hyperedges with at most \(k\) incident nodes are used. It is shown that for \(k\)-connected hypergraphs having hyperedges of rank \(k\) only (so-called \(k\)-hypergraphs) the membership problem is devidable in cubic time. This extends the corresponding result for the graph case (that is, for \(k=2\)) given by \textit{W. Vogler} [Lect. Notes Comput. Sci. 532, 676-687 (1991; Zbl 0769.68078)]. The result is based a theorem providing a unique decomposition of \(k\)-connected \(k\)-hypergraphs into components of two different kinds, which is a generalization of a 1937 result by \textit{S. MacLane} [A structural characterization of planar combinatorial graphs, Duke Math. J. 3, 460-472 (1937; Zbl 0017.42702)], who treated the case of biconnected graphs. The decomposition result allows to adapt the well-known algorithm by \textit{Coke}, \textit{Kasami}, and \textit{Younger} for context free string languages recognition to the case of hyperedge-replacement languages. It can be shown [Inf. Proc. Letters 45, 89-94 (1993)] that the restriction to \(k\)-hypergraphs is really necessary (assuming \(P\neq NP\)): There are \(NP\)-complete \(3\)-connected graph languages generated by hyperedge-replacement grammars of order 3.