  Line planning, i.e. choosing paths which are operated by one vehicle
end-to-end, is an important aspect of public transport planning. While there
exists heuristic procedures for generating lines from scratch, most theoretical
observations consider the problem of choosing lines from a predefined line
pool. In this paper, we consider the complexity of the line planning problem
when all simple paths can be used as lines. Depending on the cost structure, we
show that the problem can be NP-hard even for paths and stars and that no
polynomial time approximation of sub-linear performance is possible.
Additionally, we identify polynomially solvable cases and present a
pseudo-polynomial solution approach for trees.
