My friend and I are currently working on an interesting problem called the Spanner Sum Problem. To save you all the trouble and keep you focused on the article at hand, I'll try and incorporate all the relevant information here, in the blog post itself so we can have the best of ideas and inputs from your side!
Let's assume we have an Regular Un-Directed Graph G with E edges and V vertices (standard stuff). Let's take an image for reference:
Now, let's count the least number of edges needed to be traversed to go from one vertex to another. A to B takes one edge AB, A to C takes 2 edges, AB and BC. We can easily observe the rest.
Now say we convert this graph into a Spanning Tree. We will keep removing edges until there remain only V-1 vertices. Let's say the resulting spanning tree looks something like this:
Now you will notice, that the number of edges to be traversed to reach from A to B for example, has changed from 1 t0 2. Same is the case E and D and B and C where distance to go from one of these vertex to other has increased. Now keep this effect in mind as we describe the problem.
Let us define the (Minimum) Spanner Sum Problem as followsFor a spanning tree T of G, the spanner-sum is defined by ζ s (T, G) = ∑dT (u, v) where (u, v) ∈ E(G) \ E(T) and dT (u, v) denotes the distance between u and v in T. Then, the minimum spanner-sum of G is defined as ζ s (G) = minζ s (T, G) where the minimum is taken over all spanning trees T of G.
In more layman terms, the spanner sum problem deals with the issue of converting a graph to a tree, removing edges which yield a spanning tree which minimises distances from one vertex to another, trying to keep the distance the same as the original graph
Now, we came up with this algorithm which should/would in hindsight, seem pretty obvious.
- Begin by finding the smallest cycles
Finding the smallest cycle first. Disconnecting an edge from that cycle would make the least impact on the distance between 2 vertices which were connected by this removed edge in the first place. Let me illustrate with an elementary isolated example. Take 2 cycles, one of length 3 and other of length 5:
If we remove edge AB, then the distance between A and B increases from 1(AB itself) to 2 ( AC -> CB ). In the second case, when we remove edge AE, the distance from A to E increases from 1 (when AE was present) to 4 ( AB -> BC -> CD -> DE )
- Choosing what edge to remove from this cycle.
Now here is where we have made logical(subjective, nontheless) presumptions. We would love if someone would provide this some mathematical backing as we can't seem to think of a way to do so.
Remove the edge where the sum of the degrees of both it's vertices is minimum compared to all the other edges in the cycle
Now let's think why we would do so. When you have a edge who's vertices have the least degree, that would mean that this edge is a junction that is connecting LESSER number of places to lesser number of place, right? If you have an edge who's vertices have a high degree, that would mean that there are several incoming paths to vertex one and are outgoing from vertex 2. If we were to remove this edge, it would have a greater impact of the connectivity of the graph so we wouldn't want to remove it. This is why we would choose the edge whose sum of degree of vertices is minimum.
- Mark the rest of the edges of this cycle and don't remove them if encountered in future cycles.
Now when you disconnect an edge from a cycle, you mark all the other edges in the cycle. The reason to do this is as follows. Suppose that you encounter one of these edges you encountered in the smaller cycle as a part of a bigger cycle later on and decide to remove one of these. If you were to do so, you would reduce/disturb the connectivity of the smaller cycle edges you had processed before. This would essentially result in your previous calculations being rendered useless.
- Incrementally calculate the spanner sum
The spanner sum is initialised as 0. The spanner sum is essentially the distance between every adjacent vertex in the graph. Now having removed an Edge represented by endpoints V1 and V2, the only distance that has changed is that between V1 and V2, that that is simply the length of cycle-1. You can see the third image in this post (the one below the 'algorithm' heading) to see what I am saying. Basically, since we have removed an edge connecting these 2 vertices, we travel from V1 to V2 traversing all the vertices in between them in the cycle chosen for consideration. If you remove an edge from the hexagon (as shown in the 2nd example of the image), the distance between the vertices of the removed edge becomes 4 (length of cycle = 5 and minus 1).
Now, The distance between the remaining adjacent vertices in the cycle is simply 1 since they are connected to each other by an edge. The edges remaining in the cycle is again length of cycle-1. So we have 1 * length of cycle-1 added to the spanner sum.
So in totally, the spanner sum would be incremented by 2 * (length of cycle-1) every time we select a cycle for consideration.
- Repeat until V-1 Edges remain in the graph.
This is the basic procedure that needs to be repeated until V — 1** edges exist in the graph. That means that we've formed out spanning tree.
Working out an example
Here's an image where I've worked out an example i'll be explaining below
We first with start with the smallest cycles, here of size 3. All the cycles considered are circled in GREEN which indicates the order they were processed in. Cycles of same size my be processed in any order. We check the sum of degrees of vertices of an edge (marked over each edge in PURPLE) and remove the one with the least sum(removed edge marked in RED) as described in the algorithm. If there are multiple edges with the same sum, break the tie arbitrarily. Then, we mark the remaining edges of the cycle in BLUE which will form a part of the spanning tree and cannot be considered for removal if they form a part of a larger cycle later on. Simply repeat this procedure until V - 1 edges remain and stop.
To find the Smallest cycles, we use an Iterative Deepening DFS where we start with smallest depth, depth 3, to find all the smallest cycles. Once all the cycles of length 3 are over, we increase the depth to 4, 5 and so on.
Once we encounter a cycle (all the vertices have been stored in a stack of the DFS), we check the sum of vertex degrees for each vertex of the cycle, remove the one with the minimum sum, increment the spanner sum and continue.
We have attempted a sort of buggy but readable implementation. It runs on certain testcases, on some it goes into an infinite loop but we have made a fair attempt and are working on correcting the code as you are reading this :)
Here it is http://ideone.com/KDztVn
Thoughts and Help Required!
This problem is an NP Complete problem as far as we know, and we've come up with this particular heuristic algorithm. However, we can't provide any mathematical backing for our choice of removal edges.
We have done a few tests where we removed the edges with the maximum sum of vertex degrees instead of minimum as we are doing here, and the spanner sum we got in the end was much higher than this algorithm proposed. So we are inclined to believe that this greedy approach of ours seems to work out, in a heuristic sense, by showing that removal of the other extreme edge, the one with max sum of vertex degrees is not yielding a good result.
We're looking from some interesting inputs from your side, proposed improvements or maybe a completely new algorithm itself. We would be highly grateful if anyone of you could provide us direction with a mathematical proof that sort of proves in theory that this algorithm works.
Thanks for the read and looking forward to constructive discussion in the comments. Kindly feel free to point out any mistakes in the post or wherever additional explanation is required!