Efficient decision procedures for graph properties on context-free graph languages

ABSTRACT

Efficient ways of analyzing families of graphs that are generated by a certain type of context-free graph grammars are considered. These graph grammars are called cellular graph grammars. They generate the same graph families as hyperedge replacement systems, but are defined in a way that supports complexity analysis. A characteristic called “finiteness” of graph properties are defined, and combinatorial algorithms are presented for deciding whether a graph language generated by a given cellular graph grammar contains a graph with a given finite graph property. Structural parameters are introduced that bound the complexity of the decision procedure and special cases for which the decision can be made in polynomial time are discussed. Extensions to graph grammars that are not context-free are also given. Our results provide explicit and efficient combinatorial algorithms where, so far, only the existence of algorithms has been shown, or the best known algorithms are highly inefficient.

REFERENCES

• 1: Stefan Arnborg , Jens Lagergren , Detlef Seese, Easy problems for tree-decomposable graphs, Journal of Algorithms, v.12 n.2, p.308-340, June 1991 [doi>10.1016/0196-6774(91)90006-K]
• 2: M. W. Bern , E. L. Lawler , A. L. Wong, Linear-time computation of optimal subgraphs of decomposable graphs, Journal of Algorithms, v.8 n.2, p.216-235, June 1987 [doi>10.1016/0196-6774(87)90039-3]
• 3: Hans L. Bodlaender, Dynamic Programming on Graphs with Bounded Treewidth, Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.105-118, July 11-15, 1988
• 4: ~COURCELLE, B. An axiomatic definition of context-free rewriting and its apphcation to NLC ~graph grammars. Theoret. Cornput. Scl. 55, (1987), 141 181.
• 5: Bruno Courcelle, The monadic second-order logic of graphs. I. recognizable sets of finite graphs, Information and Computation, v.85 n.1, p.12-75, March 1990 [doi>10.1016/0890-5401(90)90043-H]
• 6: Hana Galperin, Succinct representation of graphs, 1982
• 7: Annegret Habel , Hans-Jörg Kreowski, May we introduce to you: hyperedge replacement, Proceedings of the 3rd International Workshop on Graph-Grammars and Their Application to Computer Science, p.15-26, December 02-06, 1986
• 8: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 9: K. Iwano , K. Steiglitz, Testing for cycles in infinite graphs with periodic structure, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.46-55, January 1987, New York, New York, United States [doi>10.1145/28395.28401]
• 10: ~JANSSENS, D., AND ROZENBERG, G. Decision problems for node label controlled graph ~grammars. J. Comput. S?t Scz. 22 (1981), 144 177.
• 11: T. Lengauer, Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs, Journal of Algorithms, v.8 n.2, p.260-284, June 1987 [doi>10.1016/0196-6774(87)90042-3]
• 12: Thomas Lengauer, Hierarchical planarity testing algorithms, Journal of the ACM (JACM), v.36 n.3, p.474-509, July 1989 [doi>10.1145/65950.65952]
• 13: Thomas Lengauer, Combinatorial algorithms for integrated circuit layout, John Wiley & Sons, Inc., New York, NY, 1990
• 14: T. Lengauer , K. W. Wagner, The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems, Journal of Computer and System Sciences, v.44 n.1, p.63-93, Feb. 1992 [doi>10.1016/0022-0000(92)90004-3]
• 15: Thomas Lengaujer , Egon Wanke, Efficient solution to connectivity problems on hierarchically defined graphs, SIAM Journal on Computing, v.17 n.6, p.1063-1080, Dec. 1988 [doi>10.1137/0217068]
• 16: ~ROSE, D.J. On simple characterizations of k-trees. Disc. Math. 7 (1974), 317-322.
• 17: ~ROBERTSON, N., AND SEYMOUR, P.D. Graph minors II. Algorithmic aspects of tree w~dth. J. ~,4lgonthms 7 (1986), 309-322.
• 18: Grzegorz Rozenberg , Emo Welzl, Boundary NLC graph grammars--basic definitions, normal forms, and complexity, Information and Control, v.69 n.1-3, p.136-167, April/May/June 1986 [doi>10.1016/S0019-9958(86)80045-6]
• 19: ~WANKE~ n. Algorithmen und Komplexitiitsanalyse ffir die Verarbeitung hierarchisch ~definierter Graphen und hierarchisch definierter Graphfamilien. Ph.D. dissertation ~Universitiit-Gesamthochschule-Paderborn, Paderborn, FRG, Nov. 1989.
• 20: Egon Wanke, Algorithms for graph problems on BNLC structured graphs, Information and Computation, v.94 n.1, p.93-122, Sept. 1991 [doi>10.1016/0890-5401(91)90035-Z]
• 21: Egon Wanke, The Complexity of Connectivity Problems on Context-Free Graph Languages (Extended Abstract), Proceedings of the International Conference on Fundamentals of Computation Theory, p.470-479, August 21-25, 1989
• 22: E. Wanke , M. Wiegers, Undecidability of the bandwidth problem on linear graph languages, Information Processing Letters, v.33 n.4, p.193-197, December 1989 [doi>10.1016/0020-0190(89)90140-3]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Grammar types (e.g., context-free, context-sensitive); Decision problems

General Terms:
Algorithms, Languages, Theory

Keywords:
hyperedge replacement systems