Luo, Junjie ;
Molter, Hendrik ;
Suchý, Ondrej
A Parameterized Complexity View on Collapsing kCores
Abstract
We study the NPhard graph problem Collapsed kCore where, given an undirected graph G and integers b, x, and k, we are asked to remove b vertices such that the kcore of remaining graph, that is, the (uniquely determined) largest induced subgraph with minimum degree k, has size at most x. Collapsed kCore 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 kCore is a generalization of rDegenerate Vertex Deletion (which is known to be NPhard for all r >=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 rdegenerate, that is, every its subgraph has minimum degree at most r.
We investigate the parameterized complexity of Collapsed kCore 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 kCore for k <=2 and k >= 3. For the latter case it is known that for all x >= 0 Collapsed kCore is W[P]hard when parameterized by b. We show that Collapsed kCore is W[1]hard when parameterized by b and in FPT when parameterized by (b+x) if k <=2. Furthermore, we show that Collapsed kCore 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.
BibTeX  Entry
@InProceedings{luo_et_al:LIPIcs:2019:10208,
author = {Junjie Luo and Hendrik Molter and Ondrej Such{\'y}},
title = {{A Parameterized Complexity View on Collapsing kCores}},
booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
pages = {7:17:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770842},
ISSN = {18688969},
year = {2019},
volume = {115},
editor = {Christophe Paul and Michal Pilipczuk},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10208},
URN = {urn:nbn:de:0030drops102088},
doi = {10.4230/LIPIcs.IPEC.2018.7},
annote = {Keywords: rDegenerate Vertex Deletion, Feedback Vertex Set, FixedParameter Tractability, Kernelization Lower Bounds, Graph Algorithms, Social Network Analysis}
}
2019
Keywords: 

rDegenerate Vertex Deletion, Feedback Vertex Set, FixedParameter Tractability, Kernelization Lower Bounds, Graph Algorithms, Social Network Analysis 
Seminar: 

13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Issue date: 

2019 
Date of publication: 

2019 