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.