Thumbnail Image

The Maximum Capacity of a Line Plan is Inapproximable

Puhl, Christina; Stiller, Sebastian

Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin

We consider a basic subproblem which arises in line planning with upper capacities: How much can be routed maximally along all possible lines? The essence of this problem is the Path Constrained Network Flow (PCN) problem. We explore the complexity of this problem. In particular we show that it is as hard to approximate as MAX CLIQUE. We also show that the PCN problem is hard for special graph classes, interesting both from a complexity and from a practical perspective. Finally, we present a relevant graph class for which there is a polynomial-time algorithm.