Sub-polynomial parameterized complexity of $k$-core

Yan S. Couto, Cristina G. Fernandes

The $k$-core of a graph is its (unique) largest subgraph with minimum degree at least $k$. For any $k\ge 3$, deciding whether a given vertex belongs to the $k$-core is a P-comple…