A Note on the Traveling Preacher Problem

In this paper, we consider a problem of cost allocations for shortest roundtrips. Given a weighted graph G = (V; E), we are to nd a subset S V with a maximum weight core element for the Traveling Preacher game, i.e., a subset S V with a maximum cost allocation x(S) to the vertices, such that there is no nontrivial subset S S of vertices with a total cost allocation x(S ) exceeding the cost of a Traveling Salesman tour visiting the vertices in the subset S. This game can be considered as a variant of the so-called Traveling Salesman game, with the dierence that there is no speci ed central root node for the salesman. We show that this \Traveling Preacher Problem" can be solved in polynomial time, showing that the diculty of nding a core allocation for a combinatorial optimization problem may be caused by the existence of a special depot node, rather than being a consequence of the hardness of the optimization problem itself