In this paper we investigate the AM languages that seem to be located outside NP co-NP. We give two natural examples of such AM languages, GIP and GH, which stand for Graph Isomorphism Pattern and Graph Heterogeneity, respectively. We show that the GIP is in ΔP2 AM co-AM but is unlikely to be in NP co-NP, and that GH is in ΔP2 AM but is unlikely to be in NP co-AM. We also show that GIP is in SZK. We then discuss some structural properties related to those languages: Any language that is polynomial time truth-table reducible to GIP is in AM co-AM; GIP is in co-SZK if SZK co-SZK is closed under conjunctive polynomial time bounded-truth-table reducibility; Both GIP and GH are in DP. Here DP is the class of languages that can be expressed in the form X Y, where X NP and Y co-NP.

This paper considers the problem of finding a largest common subgraph of graphs, which is an important problem in chemical synthesis. It is known that the problem is NP-hard even if graphs are restricted to planar graphs of vertex degree at most three. By the way, a graph is called an almost tree if E(B)V(B)+ K holds for every block B where K is a constant. In this paper, a polynomial time algorithm for finding a largest common subgraph of two graphs which are connected, almost trees and of bounded vertex degree. The algorithm is an extension of a subtree isomorphism algorithm which is based on dynamic programming. Moreover, it is shown that the degree bound is essential. That is, the problem of finding a largest common subgraph of two connected almost trees is proved to be NP-hard for any K0 if degree is not bounded. The three dimensional matching problem, a well known NP-complete problem, is reduced to the problem.

Lingas developed an NC algorithm for subgraph isomorphism for connected graphs of bounded separator and bounded valence. We present an NC algorithm for computing canonical forms of graphs of bounded separator by using the similar technique.

It is known that the problem of finding a largest common subgraph is NP-hard for general graphs even if the number of input graphs is two. It is also known that the problem can be solved in polynomial time if the input is restricted to two trees. In this paper, a randomized parallel (an RNC) algorithm for finding a largest common subtree of two trees is presented. The dynamic tree contraction technique and the RNC minimum weight perfect matching algorithm are used to obtain the RNC algorithm. Moreover, an efficient NC algorithm is presented in the case where input trees are of bounded vertex degree. It works in O(log(n1)log(n2)) time using O(n1n2) processors on a CREW PRAM, where n1 and n2 denote the numbers of vertices of input trees. It is also proved that the problem is NP-hard if the number of input trees is more than two. The three dimensional matching problem, a well known NP-complete problem, is reduced to the problem of finding a largest common subtree of three trees.