Bypass strong V-structures and find an isomorphic labelled subgraph in linear time

Abstract

This paper identifies a condition for which the existence of an isomorphic subgraph can be decided in linear time. The condition is evaluated in two steps. First the host graph is analysed to determine its strong V-structures. Then the guest graph must be appropriately represented. If this representation exists, the given algorithm constructively decides the subgraph isomorphism problem for the guest and the host graph in linear time. The results applies especially to the implementation of graph rewriting systems. An isomorphic subgraph must be determined automatically in each rewriting step. Thus the efficient solution presented in this paper is an important progress for any implementation project.