On the np-completeness of certain network testing problems

✍ Scribed by S. Even; O. Goldreich; S. Moran; P. Tong

• Publisher: John Wiley and Sons
• Year: 1984
• Tongue: English
• Weight: 946 KB
• Volume: 14
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230140102

✦ Synopsis

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 t o be a transmitter, the other to be a receiver, and sending a message from the transmitter t o 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.