Can we create large k-cores by adding few edges?

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Authors

Colleges, School and Institutes

External organisations

  • University of Warwick
  • Ben-Gurion University of the Negev, Be’er Sheva, Israel

Abstract

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[1]-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.

Details

Original languageEnglish
Title of host publicationComputer Science - Theory and Applications
Subtitle of host publication13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings
EditorsVladimir V. Podolskii, Fedor V. Fomin
Publication statusPublished - 25 Apr 2018
Event13th International Computer Science Symposium in Russia, CSR 2018 - Moscow, Russian Federation
Duration: 6 Jun 201810 Jun 2018

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume10846
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Computer Science Symposium in Russia, CSR 2018
CountryRussian Federation
CityMoscow
Period6/06/1810/06/18