A Parameterized Complexity View on Collapsing k-Cores | |
Luo, Junjie2,3,4; Molter, Hendrik4; Suchy, Ondrej1 | |
刊名 | THEORY OF COMPUTING SYSTEMS |
2021-06-19 | |
页码 | 40 |
关键词 | r-Degenerate vertex deletion Feedback vertex set Fixed-parameter tractability Kernelization lower bounds Graph algorithms Social network analysis |
ISSN号 | 1432-4350 |
DOI | 10.1007/s00224-021-10045-w |
英文摘要 | We study the NP-hard graph problem Collapsed k-Core where, given an undirected graph G and integers b, x, and k, we are asked to remove b vertices such that the k-core of remaining graph, that is, the (uniquely determined) largest induced subgraph with minimum degree k, has size at most x. Collapsed k-Core was introduced by Zhang et al. (2017) and it is motivated by the study of engagement behavior of users in a social network and measuring the resilience of a network against user drop outs. Collapsed k-Core is a generalization of r-Degenerate Vertex Deletion (which is known to be NP-hard for all r >= 0) where, given an undirected graph G and integers b and r, we are asked to remove b vertices such that the remaining graph is r-degenerate, that is, every its subgraph has minimum degree at most r. We investigate the parameterized complexity of Collapsed k-Core with respect to the parameters b, x, and k, and several structural parameters of the input graph. We reveal a dichotomy in the computational complexity of Collapsed k-Core for k <= 2 and k >= 3. For the latter case it is known that for all x >= 0 Collapsed k-Core is W[P]-hard when parameterized by b. For k <= 2 we show that Collapsed k-Core is W[1]-hard when parameterized by b and in FPT when parameterized by (b + x). Furthermore, we outline that Collapsed k-Core is in FPT when parameterized by the treewidth of the input graph and presumably does not admit a polynomial kernel when parameterized by the vertex cover number of the input graph. |
资助项目 | Projekt DEAL |
WOS研究方向 | Computer Science ; Mathematics |
语种 | 英语 |
出版者 | SPRINGER |
WOS记录号 | WOS:000663468900002 |
内容类型 | 期刊论文 |
源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/58824] |
专题 | 中国科学院数学与系统科学研究院 |
通讯作者 | Luo, Junjie |
作者单位 | 1.Czech Tech Univ, Fac Informat Technol, Dept Theoret Comp Sci, Prague, Czech Republic 2.Univ Chinese Acad Sci, Sch Math Sci, Beijing, Peoples R China 3.Chinese Acad Sci, Acad Math & Syst Sci, Beijing, Peoples R China 4.TU Berlin, Fac 4, Algorithm & Computat Complex, Berlin, Germany |
推荐引用方式 GB/T 7714 | Luo, Junjie,Molter, Hendrik,Suchy, Ondrej. A Parameterized Complexity View on Collapsing k-Cores[J]. THEORY OF COMPUTING SYSTEMS,2021:40. |
APA | Luo, Junjie,Molter, Hendrik,&Suchy, Ondrej.(2021).A Parameterized Complexity View on Collapsing k-Cores.THEORY OF COMPUTING SYSTEMS,40. |
MLA | Luo, Junjie,et al."A Parameterized Complexity View on Collapsing k-Cores".THEORY OF COMPUTING SYSTEMS (2021):40. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论