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

To top

------ Links: ------

Zusatzinformationen / Extras