K-core problem shows limits of parallel algorithms on special graphs
Sub-polynomial parameterized complexity of $k$-core
Computational Complexity
Summary
The k-core of a graph is a group of connected points where each has at least k friends in the group. Figuring out if a particular point is in this group is usually a slow, step-by-step problem that can't be done quickly in parallel for large graphs. The authors looked at special graph shapes to find when this problem can be solved faster using parallel computing. They found that under certain conditions, like special ways to measure graph complexity called treewidth and pathwidth, the problem becomes easier to solve in parallel, but it still needs some minimum amount of memory.
What this means in practice
- •For parallel algorithm designers: Identify graph parameters that allow efficient parallel checking of vertex membership in k-core to optimize algorithm design.
- •For graph software developers: Use specific graph structures like chordal or interval graphs and parameter bounds to implement faster parallel k-core computations.
A theory result. No direct application yet.
Authors
Yan S. Couto, Cristina G. Fernandes
Abstract
The $k$-core of a graph is its (unique) largest subgraph with minimum degree at least $k$. For any $k \geq 3$, deciding whether a given vertex belongs to the $k$-core is a P-complete problem, meaning that it is inherently sequential and highly unlikely to admit efficient parallel algorithms, even on graphs of maximum degree $k+1$. This paper investigates alternative parameterizations of the $k$-core problem to identify conditions under which it can be placed into sub-polynomial complexity classes. We prove that the problem is in para-NC$^{2+ε}$ when parameterized by treewidth, and in para-NC$^3$ when parameterized by $k$ on chordal graphs. Furthermore, we introduce a novel NC$^{3}$ algorithm for interval graphs when $k = \mathcal{O}(\lg v(G))$, which relies on an improved parameterization by pathwidth. Finally, we establish corresponding lower bounds, demonstrating that, even with these parameterizations, computing the $k$-core remains L-hard, meaning it requires at least logarithmic space. These findings explore the boundary of parallel tractability for the $k$-core problem by highlighting the graph parameters that make it inherently sequential.