The common prefix problem on trees

We consider a problem arising in database query optimization [R. Guravannavar, S. Sudarshan, Reducing order enforcement cost in complex query plans, in: Proceedings of the 23rd IEEE International Conference on Data Engineering, ICDE-2007, pp. 856–865; R. Guravannavar, S. Sudarshan, A.A. Diwan, Ch. Sobhan Babu, Reducing order enforcement cost in complex query plans, Manuscript, November 2006. Available at http://arxiv.org/abs/cs.DB/0611094], which we call as The Common Prefix Problem. We present a PTAS for this problem, when the underlying graph is a tree with the degrees of the vertices bounded by a constant, e.g. binary tree. We then use a result of Feige and Kogan [U. Feige, S. Kogan, Hardness of approximation of the balanced complete bipartite subgraph problem, Technical report MCS04-04, Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, 2004] to show that even on star graphs the problem is hard to approximate.