Abstract Heuristic search using heuristics extracted from the delete relaxation is one of the most effective methods in planning. Since fifinding the optimal solution of the delete relaxation is intractable, various heuristics introduce independence assumptions, the implications of which are not yet fully understood. Here we use concepts from graph theory to show that in problems with unary action preconditions, the delete relaxation is closely related to the Steiner Tree problem, and that the independence assumption for the set of goals results in a tree-of-shortestpaths approximation. We analyze the limitations of this approximation and develop an alternative method for computing relaxed plans that addresses them. The method is used to guide a greedy best- fifirst search, where it is shown to improve plan quality and coverage over several benchmark domains