Open problem session on clock trees

Time: 1100 to 1230 hrs on the 26th day of February, 1999 A.D.
Venue: CS Lounge, Dept. of Computer Sc., SUNY at Stony Brook, Stony Brook, NY 11794, USA.
Scribe: Saurabh Sethia
In this session we discussed the problem of finding minimum length clock trees. A paper on this problem was presented last week by Saurabh Sethia. The problems have been found very interesting to most people and hence we have decided to continue discussing it.

A clock tree for a set of points in plane is a steiner tree with a distinguishable node called root, such that all root to leaf paths are of equal length.

The problem is to find a clock tree with minimum length clock tree. This is known to be NP-hard in general metric. Approximation algorithms are known for general metric and L1 metric with additional constraints of feasability of planar embedding of the clock tree. Nothing is known about the complexity of the problem in euclidean or L1 metric.

First question that was asked was whether the problem is NP-hard for metrics that correspond to a planar graph. No progress was however made on this.

We then started looking at the simpler problem of finding an optimal clock tree for points on a single line.

Joe Mitchell had shown last week that in this case the optimum clock tree doesn't exist but it can be approached to, as close as one wants.

Joe conjectured the following to be approaching the optimal: Place the root at mid-point of the points at the end. Divide the points into two halfs depending on whether they lie on the left or right of the root. Now find the optimal clock tree for each half and join their roots to the root.

While trying to prove this conjecture Estie Arkin suggested that:

  1. We first assume that the clock tree is binary.
  2. Then prove that all the leaves of the left kid-tree lies to the left of all the leaves of the right kid-tree. In other words, the embedding of the two kid-trees were disjoint.
  3. And then prove that division of leaves between the kids is decided by the mid-point of extreme points.
Saurabh pointed out that any clock tree can be thought of as a binary tree by introducing infinitesimal edges. He and few others also saw that if there were an optimal clock tree with the embedding of kid-trees overlapping, one can always find another optimal tree that had kid-trees whose embedding were disjoint.

We then tried to prove step 3. After a while saurabh came up with a counter example which was made concrete by Joe Mitchell who gave a counter example consisting of just five points. His five points were at a distance of 0, 1, 49, 51 and 100. The clock tree given by his algorithm was of size 149.5 but he also showed a clock tree of size 127.0 for the same set of points.

Even though we couldn't do step 3, we still can find where to split using dynamic programming. And that would give us a polynomial time algorithm (Joe Mitchell mentioned that it would be quadratic). But probably we can do better.

A conjecture that came was that the splitting between the kid-trees is probably decided by the max-gap between the leaves. We ran out of time so couldn't try to resolve this conjecture either way.

In the end we had to decide whether to continue thinking about this problem next week or to have a paper presentation. Steve Skiena, democratic as ever, put it to vote. The majority voted to continue with the problem. And this time Steve did not sabotage the vote and upheld the cause of democracy!

Hope to see you next week. Friday at 11. For yet another session of fun.