A Polynomial Time Pattern Matching Algorithm on Graph Patterns of Bounded Treewidth

Takayoshi SHOUDAI  Takashi YAMADA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E100-A   No.9   pp.1764-1772
Publication Date: 2017/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E100.A.1764
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
graph pattern matching,  partial k-tree pattern,  bounded treewidth,  hyperedge replacement,  polynomial time algorithm,  

Full Text: PDF(1.2MB)>>
Buy this Article

This paper deals with a problem to decide whether a given graph structure appears as a pattern in the structure of a given graph. A graph pattern is a triple p=(V,E,H), where (V,E) is a graph and H is a set of variables, which are ordered lists of vertices in V. A variable can be replaced with an arbitrary connected graph by a kind of hyperedge replacements. A substitution is a collection of such replacements. The graph pattern matching problem (GPMP) is the computational problem to decide whether or not a given graph G is obtained from a given graph pattern p by a substitution. In this paper, we show that GPMP for a graph pattern p and a graph G is solvable in polynomial time if the length of every variable in p is 2, p is of bounded treewidth, and G is connected.