Fomin, Fedor V. ;
Sagunov, Danil ;
Simonov, Kirill
Building Large kCores from Sparse Graphs
Abstract
A popular model to measure network stability is the kcore, that is the maximal induced subgraph in which every vertex has degree at least k. For example, kcores are commonly used to model the unraveling phenomena in social networks. In this model, users having less than k connections within the network leave it, so the remaining users form exactly the kcore. In this paper we study the question of whether it is possible to make the network more robust by spending only a limited amount of resources on new connections. A mathematical model for the kcore construction problem is the following Edge kCore optimization problem. We are given a graph G and integers k, b and p. The task is to ensure that the kcore of G has at least p vertices by adding at most b edges.
The previous studies on Edge kCore demonstrate that the problem is computationally challenging. In particular, it is NPhard when k = 3, W[1]hard when parameterized by k+b+p (Chitnis and Talmon, 2018), and APXhard (Zhou et al, 2019). Nevertheless, we show that there are efficient algorithms with provable guarantee when the kcore has to be constructed from a sparse graph with some additional structural properties. Our results are
 When the input graph is a forest, Edge kCore is solvable in polynomial time;
 Edge kCore is fixedparameter tractable (FPT) when parameterized by the minimum size of a vertex cover in the input graph. On the other hand, with such parameterization, the problem does not admit a polynomial kernel subject to a widelybelieved assumption from complexity theory;
 Edge kCore is FPT parameterized by the treewidth of the graph plus k. This improves upon a result of Chitnis and Talmon by not requiring b to be small. Each of our algorithms is built upon a new graphtheoretical result interesting in its own.
BibTeX  Entry
@InProceedings{fomin_et_al:LIPIcs:2020:12702,
author = {Fedor V. Fomin and Danil Sagunov and Kirill Simonov},
title = {{Building Large kCores from Sparse Graphs}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {35:135:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771597},
ISSN = {18688969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12702},
URN = {urn:nbn:de:0030drops127026},
doi = {10.4230/LIPIcs.MFCS.2020.35},
annote = {Keywords: parameterized complexity, kcore, vertex cover, treewidth}
}
18.08.2020
Keywords: 

parameterized complexity, kcore, vertex cover, treewidth 
Seminar: 

45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Issue date: 

2020 
Date of publication: 

18.08.2020 