Set Cover, Set Packing and Hitting Set for Tree Convex and Tree-Like Set Systems

被引:0
作者
Lu, Min [1 ]
Liu, Tian [1 ]
Tong, Weitian [2 ]
Lin, Guohui [2 ]
Xu, Ke [3 ]
机构
[1] Peking Univ, Sch Elect Engn & Comp Sci, Inst Software, Key Lab High Confidence Software Technol,Minist E, Beijing 100871, Peoples R China
[2] Univ Alberta, Dept Comp Sci, Edmonton, AB T6G 2E8, Canada
[3] Beihang Univ, Natl Lab Software Dev Environm, Beijing 100191, Peoples R China
来源
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2014) | 2014年 / 8402卷
基金
加拿大自然科学与工程研究理事会;
关键词
Tree convex set systems; tree-like set systems; set cover; set packing; hitting set; polynomial time; NP-complete; FEEDBACK VERTEX SETS;
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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.
引用
收藏
页码:248 / 258
页数:11
相关论文
共 50 条
[41]   A Quadratic Kernel for 3-Set Packing [J].
Abu-Khzam, Faisal N. .
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, 2009, 5532 :81-87
[42]   PARTIALLY POLYNOMIAL KERNELS FOR SET COVER AND TEST COVER [J].
Basavaraju, Manu ;
Francis, Mathew C. ;
Ramanujan, M. S. ;
Saurabh, Saket .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2016, 30 (03) :1401-1423
[43]   Tight Results on Minimum Entropy Set Cover [J].
Jean Cardinal ;
Samuel Fiorini ;
Gwenaël Joret .
Algorithmica, 2008, 51 :49-60
[44]   Approximation algorithms for submodular set cover with applications [J].
Fujito, T .
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2000, E83D (03) :480-487
[45]   Tight results on minimum entropy set cover [J].
Cardinal, Jean ;
Fiorini, Samuel ;
Joret, Gwenael .
ALGORITHMICA, 2008, 51 (01) :49-60
[46]   Approximation algorithms for a geometric set cover problem [J].
Brimkov, Valentin E. ;
Leach, Andrew ;
Wu, Jimmy ;
Mastroianni, Michael .
DISCRETE APPLIED MATHEMATICS, 2012, 160 (7-8) :1039-1052
[47]   Approximating the dense set-cover problem [J].
Bar-Yehuda, R ;
Kehat, Z .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2004, 69 (04) :547-561
[48]   A New Deterministic Algorithm for Dynamic Set Cover [J].
Bhattacharya, Sayan ;
Henzinger, Monika ;
Nanongkai, Danupon .
2019 IEEE 60TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2019), 2019, :406-423
[49]   Connected set cover problem and its applications [J].
Shuai, Tian-Ping ;
Hu, Xiao-Dong .
ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, PROCEEDINGS, 2006, 4041 :243-254
[50]   Computing Hitting Set Kernels By AC0-Circuits [J].
Max Bannach ;
Till Tantau .
Theory of Computing Systems, 2020, 64 :374-399