Tree size reduction with keeping distinguishability

In this paper, the problem of tree size reduction with guarantee of preserving distinguishability is studied. Given a query q and a tree T, evaluating q on T will output q(T) which is a set of nodes of T. Given two nodes a and b in T, they are said to be distinguished by some query q in T, iff exactly one of them belongs to q(T). Then, given a tree T, a query class L, and two disjoint node sets A and B of T, a subtree T^′ of T satisfies the condition of preserving distinguishability of T, iff (1) T^′ contains all nodes in A∪B, (2) for any node pair (a,b)∈A×B, if a and b can be distinguished by some query in L in T, they can also be distinguished by some query (not necessarily the same one) in L in T^′, and (3) for any node pair (a,b)∈A×B and a query q∈L, if a and b can be distinguished by q in T^′, they can also be distinguished by q in T. The tree size reduction problem considered by this paper is to determine whether there is a small enough subtree T^′ of T, such that for query class L and node sets A and B, T^′ preserves the distinguishability of T. In this paper, as an initial attempt of investigating this problem, fixing L to be a specific part of tree pattern queries which is an important practical query language on trees, the tree size reduction problem is shown to be NP-complete.