Set cover, set packing and hitting set for tree convex and tree-like set systems

Min Lu; Tian Liu; Weitian Tong; Guohui Lin; Ke Xu

doi:10.1007/978-3-319-06089-7_17

Set cover, set packing and hitting set for tree convex and tree-like set systems

Min Lu, Tian Liu, Weitian Tong, Guohui Lin, Ke Xu

Computer Science

Research output: Contribution to book or proceeding › Conference article › peer-review

7 Scopus citations

Abstract

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.

Original language	English
Title of host publication	Theory and Applications of Models of Computation - 11th Annual Conference, TAMC 2014, Proceedings
Publisher	Springer Verlag
Pages	248-258
Number of pages	11
ISBN (Print)	9783319060880
DOIs	https://doi.org/10.1007/978-3-319-06089-7_17
State	Published - 2014
Event	Annual Conference on Theory and Applications of Models of Computation - Chennai, India Duration: Apr 11 2014 → Apr 13 2014 Conference number: 11 https://link.springer.com/book/10.1007/978-3-319-06089-7

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8402 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	Annual Conference on Theory and Applications of Models of Computation
Abbreviated title	TAMC
Country/Territory	India
City	Chennai
Period	04/11/14 → 04/13/14
Internet address	https://link.springer.com/book/10.1007/978-3-319-06089-7

Scopus Subject Areas

Theoretical Computer Science
General Computer Science

Keywords

-complete
hitting set
polynomial time
set cover
set packing
Tree convex set systems
tree-like set systems

Access to Document

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

Cite this

Lu, M., Liu, T., Tong, W., Lin, G., & Xu, K. (2014). Set cover, set packing and hitting set for tree convex and tree-like set systems. In Theory and Applications of Models of Computation - 11th Annual Conference, TAMC 2014, Proceedings (pp. 248-258). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8402 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-06089-7_17

Lu, Min ; Liu, Tian ; Tong, Weitian et al. / Set cover, set packing and hitting set for tree convex and tree-like set systems. Theory and Applications of Models of Computation - 11th Annual Conference, TAMC 2014, Proceedings. Springer Verlag, 2014. pp. 248-258 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9fd8b010406b4a6dbc4ddf77b5c34e0b,

title = "Set cover, set packing and hitting set for tree convex and tree-like set systems",

abstract = "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.",

keywords = "-complete, hitting set, polynomial time, set cover, set packing, Tree convex set systems, tree-like set systems",

author = "Min Lu and Tian Liu and Weitian Tong and Guohui Lin and Ke Xu",

year = "2014",

doi = "10.1007/978-3-319-06089-7_17",

language = "English",

isbn = "9783319060880",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "248--258",

booktitle = "Theory and Applications of Models of Computation - 11th Annual Conference, TAMC 2014, Proceedings",

address = "Germany",

note = "Annual Conference on Theory and Applications of Models of Computation ; Conference date: 11-04-2014 Through 13-04-2014",

url = "https://link.springer.com/book/10.1007/978-3-319-06089-7",

}

Lu, M, Liu, T, Tong, W, Lin, G & Xu, K 2014, Set cover, set packing and hitting set for tree convex and tree-like set systems. in Theory and Applications of Models of Computation - 11th Annual Conference, TAMC 2014, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8402 LNCS, Springer Verlag, pp. 248-258, Annual Conference on Theory and Applications of Models of Computation, Chennai, India, 04/11/14. https://doi.org/10.1007/978-3-319-06089-7_17

Set cover, set packing and hitting set for tree convex and tree-like set systems. / Lu, Min; Liu, Tian; Tong, Weitian et al.
Theory and Applications of Models of Computation - 11th Annual Conference, TAMC 2014, Proceedings. Springer Verlag, 2014. p. 248-258 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8402 LNCS).

Research output: Contribution to book or proceeding › Conference article › peer-review

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

N1 - Conference code: 11

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 - Annual Conference on Theory and Applications of Models of Computation

Y2 - 11 April 2014 through 13 April 2014

ER -

Lu M, Liu T, Tong W, Lin G, Xu K. Set cover, set packing and hitting set for tree convex and tree-like set systems. In Theory and Applications of Models of Computation - 11th Annual Conference, TAMC 2014, Proceedings. Springer Verlag. 2014. p. 248-258. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-06089-7_17

Set cover, set packing and hitting set for tree convex and tree-like set systems

Abstract

Publication series

Conference

Scopus Subject Areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this