Minimum spanning tree for pairs of adjacent edges

user_2244662 0
Viewed 145

For some graph, there is a cost associated with each pair of adjacent edges. I hope to find a subgraph such that every point is connected and the cost is minimised (a minimum spanning tree).

graph, with edges AB, BC, CD, and DA. ABC costs 15, BCD costs 13, CDA costs 63, DAB costs 81

For the above example, the solution will include the edges AB, BC and CD, but not DA, avoiding the expensive CDA and DAB triplets, and getting a score of 28 (weight of ABC + BCD).

To motivate this question, let's imagine that we're designing a road network between places, and whenever a car turns around a sharp bend it slows down. Creating the ideal network, one with a small number of sharp bends, may benefit from us taking node triplets into account.

The graphs I intend to apply this algorithm to will have 5,000 to 20,000 nodes, and 15,000 to 80,000 edges. Presumably, the function will be of this type or similar:

(
  nodes: [T],
  edges: [(int, int)],
  distance: (a: T, b: T, c: T) => float
) => [(int, int)]

Where b is connected to both a and c, but a and c are not necessarily connected.

What algorithm solves this problem?

Thank you for any help you may give.

minimum-spanning-tree dynamic-programming graph-theory optimization algorithm
1 Answers

The quadratic objective feels like enough leeway to construct gadgets for an NP-hardness reduction, though I have no proof at this time.

Since your graph is sparse, I’m hoping that the max degree is small, especially given your comment about road networks. I’d suggest the following integer programming formulation:

  • Variables: for each edge {v, w}, let there be a 0-1 variable x(v, w) that is 1 if {v, w} belongs to the spanning tree and 0 otherwise. Also, for each vertex v and each nonempty subset S of edges incident to e, let there be a 0-1 variable y(v, S) that is 1 if the subset of edges incident to e in the tree is S and 0 otherwise.

  • Objective: minimize ∑v,S ∑{u,w}⊆S distance(u, v, w) y(v, S).

  • Initial constraints: we require that ∑v,S y(v, S) = 1, that is, each vertex has to choose exactly one neighborhood in the tree. We also require for each edge {v, w} that ∑v,S∋w y(v, S) = x(v, w), that is, the neighborhood that v chooses has to be consistent with whether the edge exists.

  • Connectivity constraints: right now nothing forces the solver to choose any edges at all. It’s possible to formulate connectivity constraints statically, but instead I’d recommend the following approach. Run the solver with the constraints so far and compute its connected components. If there’s exactly one component, great, it’s the optimal solution. Otherwise, for each component C, require that ∑{v,w}∈E(C,V∖C) x(v, w) ≥ 1 – that is, the tree contains at least one edge with one endpoint in C and one endpoint not in C – and try again.

I usually use OR-Tools because it’s the preferred library where I work, but you have many options.

user_21446690
Related