MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a graph $G=(V,E)$ with real-valued (positive or negative) weights assigned to its edges, we want to remove a set of edges so that the sum of the remaining edges is minimized and the degree of any vertex should be different than 1 (i.e. 0 or more than 1) in the final graph.

I'm interested in the complexity of this problem.

Note that this problem is a slight variation of this.

share|cite|improve this question
So there should be no leaf vertices in the final graph. Isolated vertices are OK. – eakbas Apr 9 '10 at 1:10

It's not quite the same, but I think it's very similar to the "minimum subgraph of minimum degree ≥ d" problem in this paper, and like that problem is very likely to be NP-complete.

share|cite|improve this answer
Didn't you show in you answer to the linked question that "minimum subgraph of degree $\ge 2$" is polynomial? – Sergei Ivanov Apr 9 '10 at 8:41
The difference is that in this case one has to decide which vertices to include, and which to give degree zero. That makes it harder. – David Eppstein Apr 9 '10 at 17:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.