Hardness of Learning Unordered Tree Contraction Patterns

摘要

A tree contraction pattern (TC-pattern) is an unordered tree-structured pattern common to given unordered trees, which is obtained by merging every uncommon connected substructure into one vertex by edge contraction. In order to extract meaningful and hidden knowledge from tree structured documents, we consider a minimal language (MINL) problem for TC-patterns. The MINL problem for TC-patterns is to find one of the minimally generalized TC-pattern that are matched by all given unordered trees. Recently, Yoshimura and Shoudai (2013) showed that the MINL problem for the class of TC-patterns with a constant parameter is computable in polynomial time. In this paper, we discuss two optimization versions of the MINL problem, and show that the two problems are NP-complete.