0
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ So there should be no leaf vertices in the final graph. Isolated vertices are OK. $\endgroup$
    – eakbas
    Commented Apr 9, 2010 at 1:10

1 Answer 1

Reset to default
1
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .