Choosing spanning trees to maximise node connectivity

Question

Given: n variables in X, and m sets of variables where each set, C_i contains a subset of X. I am trying to generate the graph G = (X, E) by picking the edges in E given the following constraints.

• Variables in each set C_i must be connected by a spanning tree (no extra edges).
• The graph should prefer spanning tree configurations so that the variance of the degrees of all nodes is maximised.
• Following the previous constraint, prefer spanning tree configurations such that the degrees of nodes have greater variance, rather than average all around. So given the choice between configurations resulting in nodes of degree 1, 2, 3 vs 2, 2, 2. Prefer 1, 2, 3.

X = {x₁, x₂, x₃, x₄, x₅, x₆}

C₁ = {x₁, x₂, x₃}

C₂ = {x₂, x₄}

C₃ = {x₄, x₅}

C₄ = {x₃, x₅, x₆}

The optimal solution for the given variables is:

Each subset of variables C_i is connected by a spanning tree, and the degree of x₃ is maximised. x₃ has a maximised degree, and there are nodes with degrees of 1 (preferred).

There are a few things I am having trouble with.

1. Actually defining the problem: this graph is a constraint graph which is to be processed under some tree decomposition or cycle cutset algorithm. Variables in each set C_i share a common attribute. I am trying to remove redundant constraints so that I can get a favourable tree structure, under some ordering, for the next stage. I'm wondering if this preprocessing step is a known problem.

2. Efficiently implementing this preprocessing step. I am thinking that it may be able to be reformulated as trying to minimise the average all pairs shortest paths, and then if there is a tie, pick the one with the greatest variance. And if this is the case, whether there is an efficient algorithm to do this.

EDIT: A simpler example without cycles.

X = {x₁, x₂, x₃, x₄}

C₁ = {x₁, x₂}

C₂ = {x₂, x₃, x₄}

There is a spanning tree between, x₁ and x₂ for C₁.

This image shows the graph if I chose all the edges instead of just the spanning tree. It is undesirable as I am trying to minimise the edges, and there is an avoidable cycle.

If I didn't create the x₂ to x₃ edge, the graph would have the minimal edges satisfied, but not optimal as x₂ has a degree of 2. When choosing to not create the x₃ to x₄ edge, x₂ has a degree of 3.

If I summed the degrees in both cases they are 6. But the second case has a greater variance in the degrees (which is preferred). This is where the concept of dependency comes in, if x₂ is removed in the second case, all other nodes are disconnected. In the first case, there would still be an edge between x₃ to x₄.

Answer 1

My suggestion would be to try simulated annealing. This looks like a good candidate for that heuristic. It sounds like you have some idea what the objective function you want to minimize is (that's good; you need one).

I would suggest that you use simulated annealing as follows:

• A state is a possible graph (a set of edges).

• The cost function for a state might be your objective function plus some penalty for the number of $C_i$'s that aren't fully connected.

• To transition between states, you might randomly choose among the following options:

  • Add an edge chosen at random (or: choose a $C_i$ that isn't fully connected, and add a randomly chosen edge between some pair of variables $C_i$ that aren't currently in the same connected component)

  • Delete an edge chosen at random

  • Pick an existing edge $(u,v)$, delete the edge, then randomly choose some other variable $w$ that is in the same connected component as $v$ and add the edge $(u,w)$.

but of course you can play around with it and try different variations to see which works the best. This might just give you some reasonable solutions.

---

You could also try formulating this as a SAT or ILP instance, but my sense is that I would try simulated annealing first. If you're lucky, it just might work well enough that you don't need to bother with anything else.