2026-07-24T18:31:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10208 2024-03-06T10:44:15Z ddc:004 open_access

A Parameterized Complexity View on Collapsing k-Cores Luo, Junjie Molter, Hendrik Suchý, Ondrej r-Degenerate Vertex Deletion Feedback Vertex Set Fixed-Parameter Tractability Kernelization Lower Bounds Graph Algorithms Social Network Analysis 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. [AAAI 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. We show that Collapsed k-Core is W[1]-hard when parameterized by b and in FPT when parameterized by (b+x) if k <=2. Furthermore, we show 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Junjie Luo and Hendrik Molter and Ondrej Suchý 2019 Is Part Of LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2018.7 urn:nbn:de:0030-drops-102088 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.7 eng https://creativecommons.org/licenses/by/3.0/legalcode