On the np‐completeness of certain network testing problems

Abstract 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 endpoints 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 several 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 “phase” we mean a period in which some tests are conducted simultaneously. We show that in most models, including the “natural” model of radio communication, both problems are NP‐hard. In some models the problems can be solved by reducing them to either a maximum matching problem or an edge coloring problem for which polynomial algorithms are known. One model remains for which the complexity of the minimization problem is unknown.