The complexity of the \(K_{n,n}\)-problem for node replacement graph languages. (English) Zbl 1005.68089
Summary: The bounded \(K_{n,n}\)-problem is the question of whether or not a graph language of a given graph grammar contains arbitrarily large complete bipartite subgraphs \(K_{n,n}\). In this paper, we investigate the complexity of this problem for all relevant classes of node replacement graph grammars. Our main result states that the bounded \(K_{n,n}\)-problem is NL-complete for reduced nonblocking eNCE graph grammars and for reduced linear NCE graph grammars. As an application, our results settle the complexity of the problems of whether or not the graph language of a given confluent, boundary, or linear graph grammar has bounded tree-width and whether or not it is an HR graph language.
MSC:
| 68Q45 | Formal languages and automata |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q42 | Grammars and rewriting systems |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
References:
| [1] | Arnborg, S.; Lagergren, J.; Seese, D., Easy problems for tree-decomposable graphs, J. Algorithms, 12, 308-340 (1991) · Zbl 0734.68073 |
| [2] | Bauderon, M.; Courcelle, B., Graph expressions and graph rewritings, Math. Syst. Theory, 20, 83-127 (1987) · Zbl 0641.68115 |
| [3] | Bodlaender, H., A linear time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25, 1305-1317 (1996) · Zbl 0864.68074 |
| [4] | Bodlaender, H., A partial k-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci., 209, 1-45 (1998) · Zbl 0912.68148 |
| [5] | Courcelle, B., An axiomatic definition of context-free rewriting and its application to NLC graph grammars, Theoret. Comput. Sci., 55, 141-181 (1987) · Zbl 0644.68095 |
| [6] | Courcelle, B., Structural properties of context-free sets of graphs generated by vertex replacement, Inform. Comput., 116, 275-293 (1995) · Zbl 0828.68091 |
| [7] | Courcelle, B.; Engelfriet, J.; Rozenberg, G., Handle-rewriting hypergraph grammars, J. Comput. System Sci., 46, 218-270 (1993) · Zbl 0825.68446 |
| [8] | Engelfriet, J., Context-free NCE graph grammars, (Csirik, J.; Demetrovics, J.; Gécseg, F., Fundamentals of Computation Theory (1989)), 148-161 · Zbl 0756.68070 |
| [9] | Engelfriet, J.; Leih, G., Inform. and Comput., 81, 88-121 (1989) · Zbl 0684.68088 |
| [10] | Engelfriet, J.; Leih, G.; Welzl, E., Boundary graph grammars with dynamic edge relabeling, J. Comput. System Sci., 40, 307-345 (1990) · Zbl 0694.68049 |
| [11] | Engelfriet, J.; Rozenberg, G., A comparison of boundary graph grammars and context-free hypergraph grammars, Inform. and Comput., 84, 163-206 (1990) · Zbl 0706.68067 |
| [12] | Engelfriet, J.; Rozenberg, G.; Rozenberg, G., Node replacement graph grammars, Handbook of Graph Grammars and Computing by Graph Transformations (1997), World Scientific: World Scientific Singapore, p. 1-94 · Zbl 0908.68095 |
| [13] | Habel, A., Hyperedge Replacement: Grammars and Languages (1992), Springer-Verlag: Springer-Verlag New York/Berlin · Zbl 0787.68066 |
| [14] | Immerman, N., Languages that capture complexity classes, SIAM J. Comput., 16, 760-778 (1987) · Zbl 0634.68034 |
| [15] | Janssens, D.; Rozenberg, G., On the structure of node label controlled graph languages, Inform. Sci., 20, 191-216 (1980) · Zbl 0452.68073 |
| [16] | Janssens, D.; Rozenberg, G., Restrictions, extensions, and variations of NLC grammars, Inform. Sci., 20, 217-244 (1980) · Zbl 0452.68074 |
| [17] | Janssens, D.; Rozenberg, G.; Welzl, E., The bounded degree problem for NLC graph grammars is decidable, J. Comput. System Sci., 33, 415-422 (1986) · Zbl 0625.68057 |
| [18] | Kaul, M., Syntaxanalyse von Graphen bei Präzedenz-Graphgrammatiken (1985), Universität Osnabrück: Universität Osnabrück Osnabrück · Zbl 0587.68076 |
| [19] | Nagl, M., Formal languages of labelled graphs, Computing, 16, 113-137 (1976) · Zbl 0333.68054 |
| [20] | Skodinis, K.; Möhring, R., The bounded tree-width problem of context-free graph languages, (Möhring, R., Proc. of Graph-Theoretic Concepts in Computer Science (1997), Springer-Verlag: Springer-Verlag New York/Berlin), 303-317 · Zbl 0890.68082 |
| [21] | Skodinis, K.; Wanke, E., Emptiness problems of eNCE graph languages, J. Comput. System Sci., 51, 472-485 (1995) · Zbl 0839.68057 |
| [22] | Skodinis, K.; Wanke, E., The bounded degree problem for eNCE graph grammars, Inform. and Comput., 135, 15-35 (1997) · Zbl 0879.68069 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
