TY - GEN
T1 - On the complexity of extracting subtree with keeping distinguishability
AU - Liu, Xianmin
AU - Cai, Zhipeng
AU - Miao, Dongjing
AU - Li, Jianzhong
N1 - Publisher Copyright:
© Springer International Publishing AG 2016.
PY - 2016
Y1 - 2016
N2 - 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 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 ∪ 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 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 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 (introduced later), the subtree extraction problem is shown to be NP-complete.
AB - 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 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 ∪ 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 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 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 (introduced later), the subtree extraction problem is shown to be NP-complete.
KW - Computational complexity
KW - Distinguishability
KW - Subtree extraction
UR - https://www.scopus.com/pages/publications/85007173623
U2 - 10.1007/978-3-319-48749-6_17
DO - 10.1007/978-3-319-48749-6_17
M3 - 会议稿件
AN - SCOPUS:85007173623
SN - 9783319487489
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 230
EP - 240
BT - Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Proceedings
A2 - Li, Minming
A2 - Wang, Lusheng
A2 - Chan, T-H. Hubert
PB - Springer Verlag
T2 - 10th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2016
Y2 - 16 December 2016 through 18 December 2016
ER -