Let G(V,E) be an undirected graph which describes the structure of a communication network. During the maintenance period every line must be tested in each of the two possible directions. A line is tested by assigning one of its end-points to be a transmitter, the other to be a receiver and sending a message from the transmitter to the receiver through the line.
We define axiomatically 12 different models for communication networks all subject to the two following axioms: a vertex cannot act as a transmitter and as a receiver simultaneously and a vertex cannot receive through two lines simultaneously. In each of the models two problems arise: "What is the maximum number of lines one can test simultaneously?" and "What is the minimum number of phases necessary for testing the entire network?", where by a "phase" we mean a period in which some tests are conducted simultaneously.
We show that in 8 of the above models, including the "natural" model of radio communication, both problems are NP-Hard. In 3 other models the problems can be solved by reducing them to either a maximum matching problem or to an edge coloring problem; for 5 of the 6 resulting problems, polynomial algorithms are known while for the remaining problem the complexity is unknown. In the remaining model both problems are trivial.
Finally, we consider two additional topics concerning the minimization problems; the question of the gap between the lower bound and the upper bound for these problems and the failure of the greedy approach to solve them.
Submitted to the Senate of the Technion, February 1982.
Back to Oded Goldreich's homepage.