Sub-polynomial parameterized complexity of -core
En palabras de los autores
The -core of a graph is its (unique) largest subgraph with minimum degree at least . For any , deciding whether a given vertex belongs to the -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 . This paper investigates alternative parameterizations of the -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 when parameterized by treewidth, and in para-NC when parameterized by on chordal graphs. Furthermore, we introduce a novel NC algorithm for interval graphs when , which relies on an improved parameterization by pathwidth. Finally, we establish corresponding lower bounds, demonstrating that, even with these parameterizations, computing the -core remains L-hard, meaning it requires at least logarithmic space. These findings explore the boundary of parallel tractability for the -core problem by highlighting the graph parameters that make it inherently sequential.
Apareció: miércoles, 23 de septiembre. arXiv. Preprint, todavía sin revisión por pares.