direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

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

Zusatzinformationen / Extras