M.Sc Thesis

M.Sc StudentGlikson Alexander
SubjectVerification of Generally Intractable Graph Properties on
Graphs Generated by Graph Grammars
DepartmentDepartment of Computer Science
Supervisor PROFESSOR EMERITUS Johann Makowsky


Graph grammars are natural generalization of string grammars to graph-like relational structures. In particular, there are two well-known types of context-free graph grammars: vertex-replacement graph grammars, and edge-replacement graph grammars. Both of them use a substitution mechanism, allowing one to replace a nonterminal vertex or edge by some graph, associated with one of the productions of the grammar.

Another way to characterize graph classes is using graph operations and Finite Model Theory, which provide a uniform notational system for representation of graphs using parse terms. Two such characterizations are treewidth and clique-width of graphs. In both cases, bounded treewidth or clique-width implies that it is possible to represent the input graph by some tree or algebraic expression. Those tree-like representations can then be used in order to apply various algorithms using dynamic programming.

We investigate the explicit relationship between various types of Neighborhood Controlled Embedding (NCE) graph grammars, and treewidth and clique-width of graphs generated by them. We show that all the graphs, generated by any given NCE graph grammar, have an explicitly computable bounded clique-width (where the bound depends only on parameters of the grammar). We also provide the corresponding algorithms (based on dynamic programming techniques) for finding clique-width expression representing the given graph, based on given derivation tree. Moreover, we obtain explicit bounds for treewidth of these graphs, in cases when such a bound exists.

Moreover, we refine the classical notion of treewidth to more accurate one, treewidth(k,m). We study some of its algorithmic properties, and provide a characterization of this notion in terms of clique-width of corresponding graphs.