Building large k-cores from sparse graphs*,**

A k-core of a graph G is the maximal induced subgraph in which every vertex has degree at least k. In the 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. While EDGE k-CORE is known to be computationally hard in general, we show that there are efficient algorithms when the k-core has to be constructed from a sparse graph with some structural properties. Our results are as follows.center dot When the input graph is a forest, EDGE k-CORE is solvable in polynomial time.center dot EDGE k-CORE is fixed-parameter tractable (FPT) when parameterized by the minimum size of a vertex cover in the input graph.center dot EDGE k-CORE is FPT when parameterized by the treewidth of the graph plus k.(c) 2022 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).

Automated summary

The study focuses on efficient algorithms for the EDGE k-CORE optimization problem, particularly in constructing k-cores from sparse graphs with structural properties. The results show that the problem can be solved in polynomial time when the input graph is a forest. Additionally, by parameterizing the problem with the minimum size of a vertex cover or the treewidth of the graph plus k, it can be solved in fixed-parameter tractable (FPT) time.