Advertisement
Published in:
2016 | OriginalPaper | Chapter
On the Complexity of Extracting Subtree with Keeping Distinguishability
Authors : Xianmin Liu, Zhipeng Cai, Dongjing Miao, Jianzhong Li
Published in: Combinatorial Optimization and Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
We consider the problem of subtree extraction with guarantee of preserving distinguishability. Given a query q and a tree T, evaluating q on T will output q(T) which is a set of nodes of T. For two nodes a and b in T, they can 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 \(\mathcal {L}\), and two disjoint node sets A and B of T, a subtree \(T'\) of T is called preserving distinguishability of T, iff (1) \(T'\) contains all nodes in \(A\cup B\), (2) for any node pair \((a,b)\in {A\times B}\), if a and b can be distinguished by some query in \(\mathcal {L}\) in T, they can also be distinguished by some query (not necessarily the same one) in \(\mathcal {L}\) in \(T'\), and (3) for any node pair \((a,b)\in {A\times B}\) and a query \(q\in \mathcal {L}\), if a and b can be distinguished by q in \(T'\), they can also be distinguished by q in T. The subtree extraction problem considered by this paper is to determine whether there is a small enough subtree \(T'\) of T, such that for query class \(\mathcal {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 \(\mathcal {L}\) to be a specific part of tree pattern queries (introduced later), the subtree extraction problem is shown to be NP-complete.