Note: this is directed at theoretical computer science / math geeks.

I can’t think of a simple algorithm or reduction, and I can’t find anything on the web.

So the problem of finding the k-core, or maximum induced subgraph with minimum degree at least k, of a graph, is solvable in polynomial time (with a very easy algorithm). But what about finding the **smallest** subgraph of a graph which has minimum degree at least k?

Does anyone know if this is NP-complete or polytime? We can phrase the question like this: given a graph G and integers k and x, is there a subgraph of size at most x with minimum degree at least k?

Anyone know this one? Note: this is **not** homework.