Abstract
In social network platforms, user engagement often depends on the activity of peers. This dependency can lead to "cascading withdrawals," where the departure of a few users triggers a chain reaction of churn. The Anchored $k$-Core (AKC) problem seeks to identify a set of "anchor" users who, if incentivized to stay, can prevent such a collapse. This paper explores the parameterized complexity of AKC, proving that the problem is W[1]-hard and remains NP-hard even on restricted graph classes like planar graphs. However, it also identifies a structural threshold at $k=7$ where the problem becomes fixed-parameter tractable on planar graphs.
The Cascading Withdrawal Problem
The $k$-core of a graph is a maximal subgraph where every vertex has at least $k$ neighbors within that subgraph. In social network modeling, the $k$-core represents a stable community where each member has enough social incentive (at least $k$ friends) to remain active. If a user's active friend count falls below $k$, they leave, potentially causing others to fall below the threshold.
To mitigate this, platform providers can "anchor" a subset of users. An anchored user remains in the network regardless of their degree. The Anchored $k$-Core problem asks: given a budget $b$ of anchors, can we ensure a core of size at least $p$?
Computational Hardness and Parameterized Complexity
Previous research established that AKC is NP-hard. This work delves deeper using parameterized complexity to determine if the problem is solvable efficiently when certain parameters are small.
A key finding is that AKC is W[1]-hard when parameterized by the target core size $p$ for $k=3$. This suggests that no algorithm can solve the problem in $f(p) \cdot n^{O(1)}$ time, making it intractable even for small target sizes. The proof involves a reduction from the CLIQUE problem, utilizing a complex grid-like construction of vertex groups.
Planarity is No Shield
Many graph problems that are NP-hard in general become easy (polynomial-time solvable) when restricted to planar graphs. However, this paper demonstrates that AKC remains NP-hard on planar graphs for all $k \ge 3$. Specifically, for $k=3$, it is hard even on planar graphs with a maximum degree of 5.
The authors use a reduction from RESTRICTED-PLANAR-3-SAT, employing sophisticated gadgets to represent variables and clauses within a planar layout. This result highlights that the inherent difficulty of preventing network unraveling persists even in topologically simple networks.
The $k=7$ Threshold and Algorithmic Boundaries
Despite the broad hardness results, the authors discovered a fascinating "algorithmic boundary" in planar graphs. Due to the mathematical properties of planarity—specifically that planar graphs are sparse and cannot contain too many high-degree vertices—the problem becomes Fixed-Parameter Tractable (FPT) for $k \ge 7$.
This means that for high engagement thresholds ($k \ge 7$), there exists an algorithm with a running time of $O(f(b) \cdot n)$, where $b$ is the number of anchors. This is the first FPT algorithm for AKC on planar graphs and marks a significant transition from intractability to relative efficiency.
Conclusion and Future Work
This research significantly narrows the gap in our understanding of the AKC problem. While it proves that preventing churn is fundamentally difficult even in simple or small-scale scenarios, it also identifies specific conditions (like high $k$ in planar graphs) where efficient solutions exist.
Future research should address the remaining complexity gap for $k \in \{4, 5, 6\}$ on planar graphs. Furthermore, extending these theoretical bounds to more realistic network models, such as power-law graphs or random graphs, will be crucial for practical applications in social network management.
Summary updated