dc.contributor.author | Fomin, Fedor | |
dc.contributor.author | Sagunov, Danil | |
dc.contributor.author | Simonov, Kirill | |
dc.date.accessioned | 2021-07-06T13:10:19Z | |
dc.date.available | 2021-07-06T13:10:19Z | |
dc.date.created | 2020-09-22T16:55:26Z | |
dc.date.issued | 2020 | |
dc.Published | Leibniz International Proceedings in Informatics. 2020, 170:35 1-14. | |
dc.identifier.isbn | 978-3-95977-159-7 | |
dc.identifier.issn | 1868-8969 | |
dc.identifier.uri | https://hdl.handle.net/11250/2763607 | |
dc.description.abstract | A popular model to measure network stability is the k-core, that is the maximal induced subgraph in which every vertex has degree at least k. For example, k-cores 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 k-core. 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 k-core construction problem is the following Edge k-Core optimization problem. We are given a graph G and integers k, b and p. The task is to ensure that the k-core of G has at least p vertices by adding at most b edges. The previous studies on Edge k-Core demonstrate that the problem is computationally challenging. In particular, it is NP-hard when k = 3, W[1]-hard when parameterized by k+b+p (Chitnis and Talmon, 2018), and APX-hard (Zhou et al, 2019). Nevertheless, we show that there are efficient algorithms with provable guarantee when the k-core has to be constructed from a sparse graph with some additional structural properties. Our results are - When the input graph is a forest, Edge k-Core is solvable in polynomial time; - Edge k-Core is fixed-parameter 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 widely-believed assumption from complexity theory; - Edge k-Core 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 graph-theoretical result interesting in its own. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik | en_US |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | Building large k-cores from sparse graphs | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright the authors | en_US |
dc.source.articlenumber | 35 | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |
dc.identifier.doi | 10.4230/LIPIcs.MFCS.2020.35 | |
dc.identifier.cristin | 1832273 | |
dc.source.journal | Leibniz International Proceedings in Informatics | en_US |
dc.source.40 | 170:35 | |
dc.relation.project | Norges forskningsråd: 263317 | en_US |
dc.identifier.citation | In: Esparza, J. and Král, D. (eds.), 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), 35. | en_US |
dc.source.volume | MFCS 2020 | en_US |