# Choosing spanning trees to maximise node connectivity

Given: n variables in X, and m sets of variables where each set, Ci 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 Ci 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 = {x1, x2, x3, x4, x5, x6}

C1 = {x1, x2, x3}

C2 = {x2, x4}

C3 = {x4, x5}

C4 = {x3, x5, x6}

The optimal solution for the given variables is:

Each subset of variables Ci is connected by a spanning tree, and the degree of x3 is maximised. x3 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 Ci 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 = {x1, x2, x3, x4}

C1 = {x1, x2}

C2 = {x2, x3, x4}

There is a spanning tree between, x1 and x2 for C1.

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 x2 to x3 edge, the graph would have the minimal edges satisfied, but not optimal as x2 has a degree of 2. When choosing to not create the x3 to x4 edge, x2 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 x2 is removed in the second case, all other nodes are disconnected. In the first case, there would still be an edge between x3 to x4.

• (1) Your first paragraph says that $G$ is given, but the remainder of your question suggests that it actually is to be constructed. Which one? (2) You talk about hanging the graph as a tree, but as your example shows, it may contain cycles. How are they handled? (3) "Variables in each set must be connected by a spanning tree." -- Are there other edges between these variables allowed? – FrankW Jun 2 '14 at 10:03
• (1) Whoops, G is to be constructed. X is given, so E must be selected to finalise the graph. (2) I talk about hanging a tree, but it isn't accurate. Eventually this will undergo decomposition into a join tree. So in this case, an edge will be added between x3 and x4 to make the cycle chordal. But that is the next step of processing. It may be more accurate to say I am trying to increase the dependency on one node (in this case x3), and trying to have as few (small) cycles as possible. (3) Other edges are allowed. The spanning tree is the minimal requirement. – fli Jun 2 '14 at 13:04
• (i) How big is $n$, $m$, and the typical size of a set $C$? (typically) This will affect what kinds of algorithms are possible. (ii) I suspect this might be NP-hard, so you might need to consider heuristics, approximation algorithms, or exponential-time algorithms. Do you have any preference among those choices? (iii) Have you tried implementing any strategies so far, to see how well they work? (iv) It'll probably be possible to formulate this as a SAT or ILP instance, then apply an off-the-shelf solver. That's one approach you could try. – D.W. Jun 2 '14 at 19:41
• (v) It sounds like you have an optimization problem where you are trying to optimize (e.g., maximize) multiple different metrics at once. Usually that isn't well-defined, because it's not well-defined how to trade off between the different metrics. Do you have specific ideas for how to form a single objective function we could maximize? Or is anything reasonable worth trying? (vi) I confess I don't understand your response (2). What does it mean to increase the dependency on one node? – D.W. Jun 2 '14 at 19:43
• (i) potentially many(100s, thousands). But typically, n is in the range of <10 to low 10s. m is typically less than n. and |C| is typically 2-5. (ii) A best guess would be good enough, as long as it is close to optimal. (iii) I've implemented a strategy which takes into account the potential sums of degrees of the neighbours of each node, and prefers edges which make nodes more connected, but I don't think this is the best way to do it. (iv) I'll investigate that. – fli Jun 3 '14 at 5:14

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.

• Thanks @D.W. I think I have a better understanding of my problem now. I would like to pick the spanning trees (so that there are a minimal amount of edges and every state will have the same amount of edges) such that the variance in the degree of all nodes is maximised. As I have a defined objective function, simulated annealing still looks like a good candidate for solving this, but with my better defined problem, is there anything else you would recommend to try? Nevertheless, I'm going to try an implementation before I accept this answer. Thanks! – fli Jun 3 '14 at 12:14
• @fli, not really. If simulated annealing doesn't work, and neither SAT nor ILP work out well, I suppose you could look into tabu search -- though I don't really have any reason to expect it to work well, and it's more of a "well, I guess if you don't have any other idea what else to try..." sort of suggestion. Sorry I don't have better ideas for you. Trying an implementation before accepting this answer is definitely a good idea; that's the best way to find out whether it'll work or whether it's useless. Good luck! – D.W. Jun 3 '14 at 18:12