On the Complexity of Optimal Hotlink Assignment

The concept of hotlink assignment aims at reducing the navigation effort for users of a web directory or similar structure by inserting a limited number of additional hyperlinks called hotlinks. Given an access probability distribution of the leaves of the tree representing the web site, the goal of hotlink assignment algorithms is to minimize the expected path length between the root and the leaves. We prove that this optimization problem is NP-hard, even if only one outgoing hotlink is allowed for each node. This answers a question that has been open since the first formulation of the problem in Bose et al. (Proceedings of 11th International Symposium on Algorithms and Computation (ISAAC), 2000) nine years ago. In this work we also investigate the model where hotlinks are only allowed to point at the leaves of the tree. We demonstrate that for this model optimal solutions can be computed in O(n ²) time. Our algorithm L-OPT also operates in a more general setting, where the maximum number of outgoing hotlinks is specified individually for each node. The runtime is then O(n ³). Experimental evaluation shows that L-OPT terminates within less than one second on problem instances having up to half a million nodes.