TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 19.07.2018


Page Content

to Navigation

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ý.



Hendrik Molter
TEL 512

Back to the research colloquium site.

To top


Quick Access

Schnellnavigation zur Seite über Nummerneingabe