2020/02/18 by Fedor V. Fomin, Fomin, Fedor V., Danil Sagunov +3 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Advanced Optical Network Technologies #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2.0 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2002.07612
openalex publication_date 2020/02/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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 being 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 1) When the input graph is a forest, Edge k-Core is solvable in polynomial time; 2) Edge k-Core is fixed-parameter tractable (FPT) being 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; 3) Edge k-Core is FPT parameterized by tw+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.