A graph problem - is this NP-complete?

General Questions
#1

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. :stuck_out_tongue:

#2

My initial feeling is that the smallest subgraph of a graph which has minimum degree at least k corresponds to something easy to find in the complement of G, but that’s strictly a gut feeling, and I make no claims as to how good it is.

#3

Hmm. Well, for x = k+1 the question is “does G have an x-clique?” and the clique problem is NP-complete. (There are easy algorithms scaling as N[sup]x[/sup], so if x is bounded then there are poly-time solutions, of course.)

Possibly for larger choices of x (and certainly for smaller ones :)) the question is easy.

#4

I know! It’s driving me crazy! Oh wait, never mind. This is easy.

If you have a polytime algorithm for this (call it MinKCore), you can find the size of the maximum clique (NP-complete) in polytime:

k = core number, i.e. largest core that exists;
while(the size of the smallest k-core is > k)
k–;
end while

Yay! Now I don’t have to smack my head against the wall. I thought there might be a polytime algorithm that you could do using a centroid vertex of the k-core or something. But if there were, I’d be a millionaire! :wink:

#5

Curse you, Omphaloskeptic! And thanks, too.