| On the Parameterized Complexity of Approximating Dominating Set | |
| Karthik, C. S.1; Laekhanukit, Bundit2,3; Manurangsi, Pasin4 | |
| 2018 | |
| 关键词 | Parameterized Inapproximability Dominating Set Set Cover |
| DOI | 10.1145/3188745.3188896 |
| 页码 | 1283-1296 |
| 英文摘要 | We study the parameterized complexity of approximating the k-Dominating Set (DomSet) m Set) problem where an integer k and a graph G on n vertices are given as input, and the goal is to find a dominating set of size at most F(k) . k whenever the graph G has a dominating set of size k. When such an algorithm runs in time T(k) . poly(n) (i.e., FPT-time) for some computable function T, it is said to be an F(k)-FPT-approximation algorithm for k-DomSet. Whether such an algorithm exists is listed in the seminal book of Downey and Fellows (2013) as one of the "most infamous" open problems in Parameterized Complexity. This work gives an almost complete answer to this question by showing the non-existence of such an algorithm under W[1] not equal FPT and further providing tighter running time lower bounds under stronger hypotheses. Specifically, we prove the following for every computable functions T, F and every constant epsilon > 0: |
| 会议录出版者 | ASSOC COMPUTING MACHINERY |
| 会议录出版地 | 1515 BROADWAY, NEW YORK, NY 10036-9998 USA |
| 语种 | 英语 |
| WOS研究方向 | Computer Science |
| WOS记录号 | WOS:000458175600110 |
| 内容类型 | 会议论文 |
| 源URL | [http://10.2.47.112/handle/2XS4QKH4/3336]  |
| 专题 | 上海财经大学 |
| 作者单位 | 1.Weizmann Inst Sci, Rehovot, Israel; 2.Max Planck Inst Informat, Saarbrucken, Germany; 3.Shanghai Univ Finance & Econ, Shanghai, Peoples R China; 4.Univ Calif Berkeley, Berkeley, CA 94720 USA |
| 推荐引用方式 GB/T 7714 | Karthik, C. S.,Laekhanukit, Bundit,Manurangsi, Pasin. On the Parameterized Complexity of Approximating Dominating Set[C]. 见:. |
| 个性服务 |
| 查看访问统计 |
| 相关权益政策 |
| 暂无数据 |
| 收藏/分享 |
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论