Solutions

COS 423 Solution to Problem Set No.5
Spring 2003 1. A discussion of this problem as well as a generalizations to matroids
can be found in H. Gabow and R. Tarjan, "Efficient algorithms for a
family of matroid intersection problems," J. Algorithms 5 (1984), pp.80-
131. Here is a key lemma.
Lemma: Let T1and T2 two spanning trees. For any edge [pic]there is an
edge [pic]such that both [pic]and [pic]are spanning trees.
Proof: Let p be the path in T2 joining the ends of e. Adding e to T2
and deleting any edge on p produces a tree. Delete e from T1. This
breaks T1 into two pieces. Some edge on p connects the two pieces. This
edge, f, satisfies the lemma.
For ease of description, let us color the edges incident to r red and all
other edges green. For convenience, I will assume that [pic] is connected
and that all trees have distinct total edge costs. We can remove the
first restriction by either adding dummy edges to [pic] of very high
weight, or dealing explicitly with the connected components of [pic]. We
can deal with the second restriction by breaking ties lexicographically
using an ordering on the edges. With these restrictions there is a unique
minimum k-tree for each k not exceeding d, the degree of r. Let us denote
these minimum trees by T1,T2...Td.
Let e be a red edge in [pic] Let [pic]be an edge that satisfies Lemma 1
for Tk+1 and Tk. Suppose f is red. By Lemma 1, [pic]is a [pic] Since Tk+1
is a minimum [pic] [pic] Similarly, [pic]is a k-tree, and [pic] This
means [pic] which contradicts our assumption about uniqueness of minimum
k-trees. Thus f is green. Thus [pic]is a k-tree and [pic] is a (k+1)
tree. This implies [pic]or, equivalently, [pic] which means that
[pic]since Tk+1 is (uniquely) minimum, and [pic]
Thus we can get from Tk to Tk+1 or back by the single cheapest swap.
Tree T1 consists of a single red edge and a minimum spanning tree T of
[pic]. Since T2,...Td are obtained from T1 by successively adding a red
edge and deleting a green edge, each of T1,...,Td contains only edges in
T and edges incident to r. Hence we can restrict our attention to this
set of at most 2n-2 edges, which can be found in one minimum spanning
tree computation.
We could start with T1 and work our way up to Tk, but we shall first
describe a method that starts at Td and works its way down. To find Td,
we start by including the set of red edges and running Boruvka's minimum
spanning tree algorithm with contraction until it terminates. Since
there are only [pic]edges and Boruvka's algorithm needs only [pic]passes,
at a cost of [pic]per pass, the total time is [pic] A more careful
analysis shows that the running time is [pic] each pass reduces the
number of vertices by a factor of at least 2. All cycles in the current
graph contain the vertex into which r has been contracted. This implies
that the graph is always sparse: there are at most[pic]edges, where
[pic]is the current number of vertices. The running time satisfies the
recurrence [pic]which implies[pic]
Now we shall show how to get from Td to Tk in [pic]swaps, spending time
[pic]per swap. We maintain the connected components of [pic] For each
such component, we maintain a heap of the edges with one end in the
component. We collect the minimum-weight edges, one per component heap,
into a global heap called the swap heap. The key of an edge e in the swap
heap is its weight minus the weight of the red edge f incident to the
component whose heap contains e. One step consists of finding the edge e
of minimum key in the swap heap, finding the corresponding red edge f,
and doing the swap. This converts Tj to Tj-1 by adding e and deleting f.
We need to do a delete min on the swap heap, a delete on the two
component heaps containing e, a meld of the two components heaps
previously containing e, a find min in the resulting new component heap,
and an insert into the global heap. With F-heaps (or binomial heaps), the
heap operations take [pic]time (amortized for F-heaps) per swap. We also
need a disjoint set union structure to keep track of components, but this
structure takes less than [pic]time per swap. The total time for the
[pic]swaps needed is [pic]
Note that none of the component heaps formed by melding ever contains an
edge with both ends in the component, because the only possible such edge
is the one involved in the swap, which is deleted from both component
heaps containing it before the meld; this is since T is a tree.
Now we describe a (simpler) method that starts at T1 and works its way
up. First, we start with Td (found in [pic]time as above) and shrink each
connected component of green edges to a single vertex.
All the shrunken edges are in every Tk and do not affect the computation
of minimum swaps. Now we have a graph of d+1 vertices consisting of a
tree of green edges on d vertices and d red edges, incident to the
remaining vertex. T1 consists of the green tree and the cheapest red
edge. For each green edge (v,w) we compute the best swap using it. There
are at most two possibilities: delete (v,w) and add either (r,v) or
(r,w). We keep the cheapest swap for each green edge in a heap, choose
the cheapest and do it. When a swap adds a red edge, say (r,x), we must
delete each swap using (r,x) from the heap, and for each corresponding
green edge, recompute its cheapest swap, if any, and insert it back into
the heap. Over the course of the algorithm, there are at most [pic]heap
insertions and deletions. The total running time is [pic] we do not need
a disjoint set union data structure. An alternative is to maintain
cheapest swap for each red edge, which leads to an [pic]running time but
needs a heap of green edges for each red edge as well as a global heap.
Finally, to get on [pic]algorithm, we do the swaps in batches. We start
by contracting the green connected components of Td and contracting the
single red edge in T1: this red edge is in T2,...,Td, and contracting it
affects no relevant swaps. In general we will contract red edges as we
discover that they are in the goal tree Tk. The contracted graph may be a
multigraph it can have up to two edges, one red and one green, between
each pair of vertices. In general we will have a graph with a
distinguished vertex r. All red edges are incident to r, and green edges,
connect ends of red edges, including possibly r.
Both the red edges and the green edges form trees; the red edges form the
current tree, initially Td with one red edge contracted. We do swaps to
delete red edges and add green edges. We also compute red edges that must
be in the goal tree, and contract them. Observe that a green edge only
ever has two potential swaps, one for each of the red edges incident to
its (non-r) ends. Let s be the goal number of swaps, initially [pic] The
algorithm is as follows:
While [pic] repeat the following steps:
1. For each red edge, find its smallest swap with a green edge.
2. Find the[pic]smallest swaps, and the [pic] smallest swaps.
3. Add the green edges of the [pic]smallest swaps to the goal tree T.
4. Add the red edge of all but the [pic] smallest swaps to Tk.
5. Decrease s by the number of green edges added to Tk in step 3.
6. Contract all the edges added to Tk in steps 3 and 4.
7. For each pair of vertices [pic] delete all but the cheapest red and
green edges between v and w (if they exist). The goal tree Tk contains the red edges added in Step 4 plus the initial
red edge and the original green edges corresponding to the green edges
added in Step 3 and those contracted initially.
Step 3 adds at least [pic] green edges to Tk, because a green edge is in
at most two swaps. Step 4 and the contraction guarantees that the size of
the graph when under consideration shrinks by at least a factor of two
with each iteration. One iteration takes linear time, using selection in
step 2. The overall running time is [pic]
One also needs to prove the correctness of the algorithm; namely if we do
swaps one-at-a-time, they will include the green edges added in step 3
and not the red edges added in step 4. This relies on the fact that a
green edge can only be involved in two potential swaps. For details see
the paper cited above.
2. We obtain a simple [pic]-time solution by modifying Dijkstra's single-
source shortest path algorithm, implemented using an F-heap. The key for
a vertex v is the maximum weight of an edge from a scanned vertex to v,
and the heap is a max-heap instead of a min-heap. Proving the correctness
of this method is straightforward. Unfortunately I do not know an [pic]-comparison algorithm. This is an
open research problem. I do know an [pic]- time algorithm. This algorithm
relies on selection and on an incremental search algorithm. First observe
that all we need to determine is the maximum weight w such that there is
a path from [pic] to [pic] in the subgraph containing all edges of weight
w or more. We can test for such a path in [pic]time by graph search. We
thus concentrate on determining w.
Suppose we have divided the edges into groups [pic] with all edges in Ei
having no greater weight than those in Ei+1, for [pic] We can determine
which Ei contains an edge with weight w by using on incremental search,
as follows. Add [pic] to a set L of labeled vertices. Begin with a graph
of no edges, i=0, and [pic] Repeat the following steps until [pic]
1. Add 1 to i. Add the edges in Ei to G. For each edge[pic]with
[pic]add v to L.
2. While [pic] remove some vertex v from L. For each edge (v,w),