Filling the Missing Names of Towns in a Map: A Graph Theoretic Approach

Abstract

A map shows only the names of some (but not all) towns in a region. If for each town, the names of all neighboring towns are known, when is it possible to reconstruct from this information the missing names? We deal with a generalization of this problem to arbitrary graphs. For a graph $G=(V,E)$ with $n$ nodes, we give an $O(n^3)$ algorithm to recognize those instances for which the answer is YES, as well as two characterization theorems: NO-instances are determined by the existence of a certain partition of $V$ and YES-instances by the existence of a suitable weak order in $V$.