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.

  • $\begingroup$ So there should be no leaf vertices in the final graph. Isolated vertices are OK. $\endgroup$ – 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.

  • $\begingroup$ Didn't you show in you answer to the linked question that "minimum subgraph of degree $\ge 2$" is polynomial? $\endgroup$ – Sergei Ivanov Apr 9 '10 at 8:41
  • $\begingroup$ 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. $\endgroup$ – David Eppstein Apr 9 '10 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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