The Complexity of the K_n,n -Problem for Node Replacement Graph Languages

摘要

The bounded K_n,n-problem is the question 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 grammers. 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.