Sie sind hier

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[1]-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ý.

Date
Speaker
Location
Language
19.07.2018
16:15
Hendrik Molter
TEL 512
English

Back to the research colloquium site.

To top