A Parameterized Complexity View on Collapsing k-Cores
Junjie Luo, Hendrik Molter, Ondřej Suchý · Theory of Computing Systems · 2021
Abstract We study the -hard graph problemCollapsed k-Corewhere, given an undirected graphGand integersb,x, andk, we are asked to removebvertices such that thek-core of remaining graph, that is, the (uniquely determined) largest induced subgraph with minimum degreek, has size at mostx.Collapsed k-Corewas 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-Coreis a generalization ofr-Degenerate Vertex Deletion(which is known to be -hard for allr≥ 0) where, given an undirected graphGand integersbandr, we are asked to removebvertices such that the remaining graph isr-degenerate, that is, every its subgraph has minimum degree at mostr. We investigate the parameterized complexity ofCollapsed k-Corewith respect to the parametersb,x, andk, and several structural parameters of the input graph. We reveal a dichotomy in the computational complexity ofCollapsed k-Corefork≤ 2 andk≥ 3. For the latter case it is known that for allx≥ 0Collapsed k-Coreis -hard when parameterized byb. Fork≤ 2 we show thatCollapsed k-Coreis -hard when parameterized byband in when parameterized by (b+x). Furthermore, we outline thatCollapsed k-Coreis in 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.