2026-07-23T13:52:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12702 2024-03-06T10:50:37Z ddc:004 open_access

Building Large k-Cores from Sparse Graphs Fomin, Fedor V. Sagunov, Danil Simonov, Kirill parameterized complexity k-core vertex cover treewidth 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fedor V. Fomin and Danil Sagunov and Kirill Simonov 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.35 urn:nbn:de:0030-drops-127026 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.35 eng https://creativecommons.org/licenses/by/3.0/legalcode