2013/04/23 by Chitnis, Rajesh, Fomin, Fedor V., Golovach, Petr A.
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Social and Information Networks (cs.SI)
paper · doi:10.48550/arxiv.1304.6420
The behavior of users in social networks is often observed to be affected by the actions of their friends. Bhawalkar et al. \citebhawalkar-icalp 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 ≥ 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. \citebhawalkar-icalp considered the Anchored k-Core problem: Given a graph G and integers b, k and p do there exist a set of vertices B⊆ H⊆ V(G) such that |B|≤ b, |H|≥ p and every vertex v∈ H∖ B has degree at least k is the induced subgraph G[H]. They showed that the problem is NP-hard for k≥ 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. \citebhawalkar-icalp (who show W[2]-hardness parameterized by b) as our parameter is always bigger since p≥ b. Then we answer a question of Bhawalkar et al. \citebhawalkar-icalp by showing that the Anchored k-Core problem remains NP-hard on planar graphs for all k≥ 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≥ 7.