I’m working on Algorithm Design (Kleinberg-Tardos) Chapter 1 exercise 7:

Some of your friends are working for CluNet, a builder of large

communication networks, and they are looking at algorithms for

switching in a particular type of input/output crossbar. Here is the

setup. There are n input wires and n output wires, each directed from

a source to a terminus. Each input wire meets each output wire in

exactly one distinct point, at a special piece of hardware called a

junction box. Points on the wire are naturally ordered in the

direction from source to terminus; for two distinct points x and y on

the same wire, we say that x is upstream from y if x is closer to the

source than y, and otherwise we say x is downstream from y. The order

in which one input wire meets the output wires is not necessarily the

same as the order in which another input wire meets the output wires.

(And similarly for the orders in which output wires meet input wires.)

Figure 1.8 gives an example of such a collection of input and output

wires. Now, here’s the switching component of this situation. Each

input wire is carrying a distinct data stream, and this data stream

must be switched onto one of the output wires. If the stream of Input

i is switched onto Output j, at junction box B, then this stream

passes through all junction boxes upstream from B on Input i, then

through B, then through all junction boxes downstream from B on Output

j. It does not matter which input data stream gets switched onto which

output wire, but each input data stream must be switched onto a

different output wire. Furthermore—and this is the tricky

constraint—no two data streams can pass through the same junction box

following the switching operation. Finally, here’s the problem. Show

that for any specified pattern in which the input wires and output

wires meet each other (each pair meeting exactly once), a valid

switching of the data streams can always be found—one in which each

input data stream is switched onto a different output, and no two of

the resulting streams pass through the same junction box.

Additionally, give an algorithm to find such a valid switching.

This is the algorithm I’ve came up with so far:

- Input wires prefer output wires in the order the signal meets each output wire from source to terminus.
- Output wires prefer the source input wires of downstream junctions to source input wires of upstream junctions.
- Let M be the matchings after applying the G-S algorithm using the input wires, output wires, and associated preferences
- Return the set M of input-to-output wire matchings

I’m having trouble proofing or disproving this algorithm correctly solves the problem. My goal is to show that if 2 data streams meet at the same junction then it leads to an instability in the matchings. I started by assuming the data streams meet on some arbitrary output wire and a downstream junction exists, but I haven’t made any progress past that in showing an instability. The 2 source input wires will prefer this arbitrary output wire over their terminus wire, but there is always a place on this arbirary wire to place a junction such that the arbirary output wire prefers it over the other two junctions – then no instability can exist.