6
$\begingroup$

I've come up with the following optimization problem in my research. Is this a known problem in graph-theory and/or combinatorial optimization? If not, which of the known problems are the most similar to it?

Let's have a graph $G=(V,E)$ with real positive or negative weights assigned to its edges: $w: E \rightarrow \Re$. The problem is to remove a set of edges ($E_1$) from $G$ such that the sum of the remaining edges ($E_2$) is minimized, and no vertex in G has degree less than 2 (i.e. no leaf vertices should exist).

Improve this question
$\endgroup$
2
  • $\begingroup$ I suspect Hamiltonian cycle reduces to (a subproblem of) this problem, which would make it NP-complete. Let's see what others say. Gerhard "Ask Me About System Design" Paseman, 2010.04.08 $\endgroup$
    – Gerhard Paseman
    Commented Apr 8, 2010 at 15:43
  • $\begingroup$ I posted another version of this problem here: mathoverflow.net/questions/20800/… $\endgroup$
    – eakbas
    Commented Apr 8, 2010 at 23:23

1 Answer 1

Reset to default
3
$\begingroup$

I'm not sure about published references to this specific problem, but I'm pretty sure it can be solved in polynomial time via a reduction to minimum weight perfect matching, as follows.

Replace each vertex of degree $d$ by a complete bipartite graph $K_{d-2,d}$ where each of the original edges incident to the vertex becomes incident to one of the vertices on the $d$-vertex side of the bipartition. Set all edge weights in this complete bipartite graph to zero. Next, add a complete graph (with zero edge weights) connecting all of the vertices in the whole graph that are on the $(d-2)$-vertex sides of their bipartitions.

For each vertex $v$ in the original graph, a perfect matching in this modified graph has to include at least two of the original graph's edges incident to $v$, because at least two of the vertices on the $d$-vertex side of the complete bipartite graph that replaces $v$ are not matched within that complete bipartite graph. Because all the other edges have cost zero, the cost of the perfect matching is the same as the cost of the solution it leads to in the original graph.

On the other hand, whenever one has a subgraph of the original graph that includes at least two edges at each vertex, it can be completed to a perfect matching at no extra cost by matching the remaining vertices on the $d$-vertex sides of their bipartition to vertices on the $(d-2)$-vertex sides, and then using the complete graph edges to complete the matching among any remaining unused vertices on the $(d-2)$-vertex sides.

Therefore, the cost of the minimum weight perfect matching in this graph is the same as the cost of the optimal solution to your problem.

Added later: something like this appears to be in "An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems", Hal Gabow, STOC 1983, doi:10.1145/800061.808776

Improve this answer
$\endgroup$
6
  • $\begingroup$ Just to check my intuition (and your reduction), if he in addition asked that the minimum cost graph be connected, would there be a reduction from Hamiltonian cycle? Gerhard "Ask Me About System Design" Paseman, 2010.04.08 $\endgroup$
    – Gerhard Paseman
    Commented Apr 8, 2010 at 18:33
  • $\begingroup$ Yes. Actually I think the reduction is easy: if you set all edge costs to one, then Hamiltonian cycles are exactly the same thing as connected spanning subgraphs in which every vertex has degree exactly two, which are the same thing as degree-≥2 connected spanning subgraphs with total cost at most $n$. $\endgroup$
    – David Eppstein
    Commented Apr 8, 2010 at 20:07
  • $\begingroup$ I didn't understand how the second addition, i.e. the one mentioned in the last sentence of the second paragraph, is done. $\endgroup$
    – eakbas
    Commented Apr 8, 2010 at 22:51
  • 1
    $\begingroup$ eakbas: The first part replaces each vertex v_i by a complete bipartite graph with vertices named, say, u_{i,j} (0 ≤ j < d-2) and w_{i,j} (0 ≤ j < d). The second addition simply connects every u_{i,j} and u_{i',j'} by an edge, so that any subset of the u's can be matched. $\endgroup$
    – David Eppstein
    Commented Apr 9, 2010 at 1:49
  • $\begingroup$ Where do the w_{i,j}s get connected? $\endgroup$
    – eakbas
    Commented Apr 9, 2010 at 2:06

You must log in to answer this question.

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