A Parameterized Complexity View on Collapsing (k)-Cores
Hendrik Molter (TU Berlin)
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 geq 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 leq 2) and (k geq 3). For the latter case it is known that for all (x geq 0) Collapsed (k)-Core is W[P]-hard when parameterized by (b). We show that Collapsed (k)-Core is W-hard when parameterized by (b) and in FPT when parameterized by ((b + x)) if (k leq 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.
Joint work with Junjie Luo and Ondrej Suchý.
Back to the research colloquium site.