Minimum cost algorithm with 1 cost for edges and 2 costs for vertexes

Question

I am trying to figure out an algorithm for the following situation: I want to run a minimum cost algorithm on an undirected graph. The edges have a cost associated to them, and the vertexes have 2 costs associated to which one them. This is where it gets kind of tricky. I have to pick one of the 2 costs associated to the vertex. If I choose cost1, the vertex will be of type 1, if I choose cost2, the vertex will be of type 2. Vertexes can only be considered connected by an edge IF they are of different types. Most of the time it will be logical to pick the lowest cost for the vertex, but depending of the cost of its edges associated to it, and the type of its neighbor vertex, you would prefer to pick the highest cost for the vertex, resulting on an smaller overall cost. Any sugestions like which algorithm or what methods I should try to apply would be much appreciated.

Here is a link to a simple example of what I am trying to achieve. The cost of this solution is 57, which is the lowest possible cost for this graph.

edit: Spelling.

Answer 1

The problem you describe can be trivially converted into a minimum-cut problem, and then solved with the Stoer-Wagner algorithm. Create two more vertices, each of which has edges to all other vertices (except each other). On one, the edge costs are taken from the corresponding vertices' cost1s; on the other, from their cost2s. Now find a minimum cut; this will cut between the two new nodes and partition the original vertices into type1 and type2.

EDIT: If the (original) edge costs are sufficiently high compared to the vertex costs, you may end up with the two new vertices in the same partition. To prevent that from happening, add a large equal cost to all edges added to the new vertices (greater than the sum of all other edges).