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 - http://www.scopus.com/inward/record.url?scp=84958537497&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-06089-7_17

DO - 10.1007/978-3-319-06089-7_17

M3 - Conference article

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 -