Welcome to MathOverflow

Question

0

2

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.

edited Apr 9 2010 at 0:06

asked Apr 8 2010 at 23:23

eakbas
121●6

So there should be no leaf vertices in the final graph. Isolated vertices are OK. – eakbas Apr 9 2010 at 1:10

David Eppstein · Answer 1 · 2010-04-09 01:47:20Z UTC

1

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.

answered Apr 9 2010 at 1:47

David Eppstein
9,233●1●21●41

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

Degree constrained edge partitioning (version 2)

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.