@unpublished{Thuerauf2020, author = {Johannes Th{\"u}rauf}, title = {Deciding the Feasibility of a Booking in the European Gas Market is coNP-hard}, institution = {Friedrich-Alexander-Universit{\"a}t Erlangen-N{\"u}rnberg}, year = {2020}, abstract = {We show that deciding the feasibility of a booking (FB) in the European entry-exit gas market is coNP-hard if a nonlinear potential-based flow model is used. The feasibility of a booking can be characterized by polynomially many load flow scenarios with maximum potential-difference, which are computed by solving nonlinear potential-based flow models. We use this existing characterization of the literature to prove that FB is coNP-hard by reducing Partition to the infeasibility of a booking. We further prove that computing a potential-difference maximizing load flow scenario is NP-hard even if we can determine the flow direction a priori. From the literature, it is known that FB can be decided in polynomial time on trees and a single cycle. Thus, our hardness result draws the first line that separates the easy from the hard variants of FB and finally answers that FB is hard in general.}, url = {https://opus4.kobv.de/opus4-trr154/313}, type = {Preprint}, institution = {TRR 154} }