Optimal link test patterns in networks and the Chinese Postman Problem

The problem of finding optimal link test patterns is a basic problem in Telecommunication networks. The paper shows that this problem is closely related to the well-known Chinese Postman Problem and that the latter is a relaxation of the former. It provides a family of examples showing that the Chinese Postman lower bound can be made arbitrarily bad, together with some arguments suggesting that the problem may be hard to solve. Its theoretical complexity, however, remains as an open question.