The Minimum Cost Tension problem (MCT) is a network combinatorial optimization problem which has been relatively ignored by the literature. This problem appears however in many applications concerning networks such as timing of events, location of facilities, shared cost problems, and so on.The most known algorithm for solving the minimum cost tension problem is the classical out-of-killer method which was developed by J.M. Pla in 1971. In this paper, we prove that this algorithm is non-polynomial by giving a graph family {T n , n 2}, on which it runs necessarily in an exponential number of iterations, namely 2 n + 2 n - 1 + 2 n - 2 - 2 calls to a linear labeling process. The demonstration is based on the fact that the execution on T n can be seen as divided into two main stages: the first one repeats the same execution as that on T n - 1 and the second stage undo one by one the iterations of the first stage. By analogy with Greek mythology, we called this family of instances Penelope's graphs.