AAAI Publications, Twenty-Seventh AAAI Conference on Artificial Intelligence

Font Size: 
Preventing Unraveling in Social Networks Gets Harder
Rajesh Hemant Chitnis, Fedor V. Fomin, Petr A. Golovach

Last modified: 2013-06-29


The behavior of users in social networks is often observed to be affected by the actions of their friends. Bhawalkar et al. (ICALP '12) introduced a formal mathematical model for user engagement in social networks where each individual derives a benefit proportional to the number of its friends which are engaged. Given a threshold degree k the equilibrium for this model is a maximal subgraph whose minimum degree is at least k. However the dropping out of individuals with degrees less than k might lead to a cascading effect of iterated withdrawals such that the size of equilibrium subgraph becomes very small. To overcome this some special vertices called "anchors" are introduced: these vertices need not have large degree. Bhawalkar et al. considered the Anchored k-Core problem: Given a graph G and integers b, k and p do there exist sets of vertices B, H such that B is a subset of H, size of B is at most b and size of H is at least p, and every vertex v which is in H but not in B has degree at least k in the induced subgraph G[H]. They showed that the problem is NP-hard for all k greater equal 2, and gave some inapproximability and fixed-parameter intractability results. In this paper we give improved hardness results for this problem. In particular we show that the Anchored k-Core problem is W[1]-hard parameterized by p, even for k=3. This improves the result of Bhawalkar et al.  (who show W[2]-hardness parameterized by b) as our parameter is always bigger since p is greater equal than b. Then we answer a question of Bhawalkar et al. by showing that the Anchored k-Core problem remains NP-hard on planar graphs for all k greater equal 3, even if the maximum degree of the graph is k+2. Finally we show that the problem is FPT on planar graphs parameterized by b for all k greater equal 7.


Social networks, parameterized complexity, planar graphs

Full Text: PDF