KMS Of Academy of mathematics and systems sciences, CAS
| A Parameterized Complexity View on Collapsing k-Cores | |
| Luo, Junjie1,2,3; Molter, Hendrik1; Suchy, Ondrej4 | |
| 2021-06-19 | |
| Source Publication | THEORY OF COMPUTING SYSTEMS
 |
| ISSN | 1432-4350 |
| Pages | 40 |
| Abstract | 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. |
| Keyword | r-Degenerate vertex deletion Feedback vertex set Fixed-parameter tractability Kernelization lower bounds Graph algorithms Social network analysis |
| DOI | 10.1007/s00224-021-10045-w |
| Indexed By | SCI |
| Language | 英语 |
| Funding Project | Projekt DEAL |
| WOS Research Area | Computer Science ; Mathematics |
| WOS Subject | Computer Science, Theory & Methods ; Mathematics |
| WOS ID | WOS:000663468900002 |
| Publisher | SPRINGER |
| Citation statistics | |
| Document Type | 期刊论文 |
| Identifier | http://ir.amss.ac.cn/handle/2S8OKBNM/58825 |
| Collection | 中国科学院数学与系统科学研究院 |
| Corresponding Author | Luo, Junjie |
| Affiliation | 1.TU Berlin, Fac 4, Algorithm & Computat Complex, Berlin, Germany 2.Chinese Acad Sci, Acad Math & Syst Sci, Beijing, Peoples R China 3.Univ Chinese Acad Sci, Sch Math Sci, Beijing, Peoples R China 4.Czech Tech Univ, Fac Informat Technol, Dept Theoret Comp Sci, Prague, Czech Republic |
| Recommended Citation 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. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment