In this thesis, we have analyzed the complexity of different graph problems that are all motivated by problems that arise in public transport optimization. Precisely, we have regarded the integration of the Transfer Quality Maximization Problem and the Vehicle Scheduling Problem in a Variable Timetable for existing, but ill-synchronized, timetables. The resulting graph problems are located in the fields of MAXIMUM GENERALIZED Quasi-Assignment problems, Maximum Feasible Subsystem of Linear Relations problems and Minimum Set Cover problems. Our indepth analysis demonstrates that all these problems are NP-hard, even on very restricted, seemingly trivial structures. It is hence not surprising at all that even powerful commercial solvers fail to solve instances of larger sizes. It is more than justified to approach these problems with heuristics. For various special cases, we have been able to state algorithms with a proven approximation factor. Our numerical results cannot replace an in-depth computational study, but give an insight in the behavior of the considered algorithms. As long as the LP relaxation is efficiently computable, it is a good choice to approach the integrated problem IntPr as well as the Semi-integrated Problem MTQP-FVS with LP-rounding heuristics. With increasing problem sizes and shift variability, how ever, this is not an option anymore. For the MTQP-FVS, a dynamic programing algorithm heuristic DP, which we present, delivers good and fast results also on very large instances. Unfortunately, in contrast to the MIP-based methods or a Primal-Dual heuristic, which we introduce, DP provides less modeling power for real world constraints. It is an interesting open question how the efficiency of DP can be exploited within a realistic modeling framework.