Nonempty k-Core (NE-k-Core)

Input

An undirected graph $G = (V, E)$ and an integer $k$.

Problem

Is the $k$-core of $G$ nonempty?

Definitions

The $k$-core of a graph is its maximum subgraph with minimum degree at least $k$. It is unique.

Status

$\P$-complete (Anderson and Mayr [1]).

Remarks

The reduction to show hardness is from AM2CVP, and it follows even when $k \leq 3$ (NE-3-Core) on graphs of maximum degree 4.

Let the core value $C(G)$ of $G$ be the largest $k$ such that its $k$-core is nonempty. We can consider the optimization problem of finding $C(G)$ for the graph. Note that this is exactly the degeneracy of $G$.

For any $\epsilon > 0$, there is a $(2+\epsilon)$-approximation algorithm for finding $C(G)$ [1], that is, computing $x$ such that $C(G) \leq x \leq (2+\epsilon)C(G)$. Furthermore, computing any $(2-\epsilon)$-approximation is $\P$-hard.

This is a direct variant of k-Core, though it might be easier than k-Core in some contexts. For example, NE-k-Core in chordal graphs is in $\NC$ (as it follows directly from finding maximal cliques in chordal graphs, which is in $\NC$), while k-Core on chordal graphs is open.