NP-completeness of Shortest Leaf-to-Leaf Distance in a Tree

摘要

Dissemination of information from nodes in a network to all other nodes in the network via a sequence of calls between pairs of nodes is known as gossiping. If new information can arise at any time, then a perpetual call scheme is required, and this is known as perpetual gossiping. Perpetual gossiping is a more difficult problem than its static counterpart, and this paper aims to show why. If a perpetual in-order traversal is used as a call scheme on a tree, then the efficiency of the scheme depends on the shortest leaf-to-leaf distance used in the embedding of the tree. However, for an arbitrary tree, finding an embedding with a shortest leaf-to-leaf which maximizes the efficiency of communication distance is an NP-complete problem, which shall be shown in this paper.