TY - GEN
T1 - Set cover, set packing and hitting set for tree convex and tree-like set systems
AU - Lu, Min
AU - Liu, Tian
AU - Tong, Weitian
AU - Lin, Guohui
AU - Xu, Ke
PY - 2014
Y1 - 2014
N2 - A set system is a collection of subsets of a given finite universe. A tree convex set system has a tree defined on the universe, such that each subset in the system induces a subtree. A circular convex set system has a circular ordering defined on the universe, such that each subset in the system induces a circular arc. A tree-like set system has a tree defined on the system, such that for each element in the universe, all subsets in the system containing this element induce a subtree. A circular-like set system has a circular ordering defined on the system, such that for each element in the universe, all subsets in the system containing this element induce a circular arc. In this paper, we restrict the trees to be stars, combs, triads, respectively, and restrict the set system to be unweighted. We show tractability of Triad Convex Set Cover, Circular-like Set Packing, and Triad-like Hitting Set, intractability of Comb Convex Set Cover and Comb-like Hitting Set. Our results not only complement the known results in literatures, but also rise interesting questions such as which other kind of trees will lead to tractability or intractability results of Set Cover, Set Packing and Hitting Set for tree convex and tree-like set systems.
AB - A set system is a collection of subsets of a given finite universe. A tree convex set system has a tree defined on the universe, such that each subset in the system induces a subtree. A circular convex set system has a circular ordering defined on the universe, such that each subset in the system induces a circular arc. A tree-like set system has a tree defined on the system, such that for each element in the universe, all subsets in the system containing this element induce a subtree. A circular-like set system has a circular ordering defined on the system, such that for each element in the universe, all subsets in the system containing this element induce a circular arc. In this paper, we restrict the trees to be stars, combs, triads, respectively, and restrict the set system to be unweighted. We show tractability of Triad Convex Set Cover, Circular-like Set Packing, and Triad-like Hitting Set, intractability of Comb Convex Set Cover and Comb-like Hitting Set. Our results not only complement the known results in literatures, but also rise interesting questions such as which other kind of trees will lead to tractability or intractability results of Set Cover, Set Packing and Hitting Set for tree convex and tree-like set systems.
KW - -complete
KW - hitting set
KW - polynomial time
KW - set cover
KW - set packing
KW - Tree convex set systems
KW - tree-like set systems
UR - https://www.scopus.com/pages/publications/84958537497
U2 - 10.1007/978-3-319-06089-7_17
DO - 10.1007/978-3-319-06089-7_17
M3 - 会议稿件
AN - SCOPUS:84958537497
SN - 9783319060880
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 248
EP - 258
BT - Theory and Applications of Models of Computation - 11th Annual Conference, TAMC 2014, Proceedings
PB - Springer Verlag
T2 - 11th Annual Conference on Theory and Applications of Models of Computation, TAMC 2014
Y2 - 11 April 2014 through 13 April 2014
ER -