# A graph problem - is this NP-complete?
**URL:** https://boards.straightdope.com/t/a-graph-problem-is-this-np-complete/211738
**Category:** Factual Questions
**Created:** [November 6, 2003, 6:17pm UTC](https://boards.straightdope.com/t/a-graph-problem-is-this-np-complete/211738 "2003-11-06T18:17:23Z")
**Posts on this page:** 5
**Page:** 1
### Author:  [@KarmaComa](https://boards.straightdope.com/u/KarmaComa)
#### Post date: [November 6, 2003, 6:17pm UTC](https://boards.straightdope.com/t/a-graph-problem-is-this-np-complete/211738/1 "2003-11-06T18:17:23Z")
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. 😛
---
### Author:  [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)
#### Post date: [November 6, 2003, 6:49pm UTC](https://boards.straightdope.com/t/a-graph-problem-is-this-np-complete/211738/2 "2003-11-06T18:49:15Z")
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.
---
### Author:  [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)
#### Post date: [November 6, 2003, 6:57pm UTC](https://boards.straightdope.com/t/a-graph-problem-is-this-np-complete/211738/3 "2003-11-06T18:57:09Z")
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.
---
### Author:  [@KarmaComa](https://boards.straightdope.com/u/KarmaComa)
#### Post date: [November 6, 2003, 7:06pm UTC](https://boards.straightdope.com/t/a-graph-problem-is-this-np-complete/211738/4 "2003-11-06T19:06:40Z")
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! 😉
---
### Author:  [@KarmaComa](https://boards.straightdope.com/u/KarmaComa)
#### Post date: [November 6, 2003, 7:09pm UTC](https://boards.straightdope.com/t/a-graph-problem-is-this-np-complete/211738/5 "2003-11-06T19:09:26Z")
Curse you, Omphaloskeptic! And thanks, too.