Can we create large k-cores by adding few edges?
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
Colleges, School and Institutes
- University of Warwick
- Ben-Gurion University of the Negev
The notion of a k-core, defined by Seidman [’83], has turned out to be useful in analyzing network structures. The k-core of a given simple and undirected graph is the maximal induced subgraph such that each vertex in it has degree at least k. Hence, finding a k-core helps to identify a (core) community where each entity is related to at least k other entities. One can find the k-core of a given graph in polynomial time, by iteratively deleting each vertex of degree less than k. Unfortunately, this iterative dropping out of vertices can sometimes lead to unraveling of the entire network; e.g., Schelling [’78] considered the extreme example of a path with k = 2, where indeed the whole network unravels. In order to avoid this unraveling, we would like to edit the network in order to maximize the size of its k-core. Formally, we introduce the Edge k-Core problem (EKC): given a graph G, a budget b, and a goal p, can at most b edges be added to G to obtain a k-core containing at least p vertices? First we show the following dichotomy: EKC is polytime solvable for k ≤ 2 and NP-hard for k ≥ 3. Then, we show that EKC is W-hard even when parameterized by b + k + p. In searching for an FPT algorithm, we consider the parameter “treewidth”, and design an FPT algorithm for EKC which runs in time (k + tw)O(tw+b) · poly(n), where tw is the treewidth of the input graph. Even though an extension of Courcelle’s theorem [Arnborg et al., J. Algorithms ’91] can be used to show FPT for EKC parameterized by tw + k + b, we obtain a much faster running time as compared to Courcelle’s theorem (which needs a tower of exponents) by designing a dynamic programming algorithm which needs to take into account the fact that newly added edges might have endpoints in different bags which cross the separator.
|Title of host publication||Computer Science - Theory and Applications|
|Subtitle of host publication||13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings|
|Editors||Vladimir V. Podolskii, Fedor V. Fomin|
|Publication status||Published - 25 Apr 2018|
|Event||13th International Computer Science Symposium in Russia, CSR 2018 - Moscow, Russian Federation|
Duration: 6 Jun 2018 → 10 Jun 2018
|Name||Lecture Notes in Computer Science|
|Conference||13th International Computer Science Symposium in Russia, CSR 2018|
|Period||6/06/18 → 10/06/18|