Deciding the feasibility of a booking in the European gas market is coNP-hard

We show that deciding the feasibility of a booking (FB) in the European entry-exit gasmarket 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 potentialdifference, which are computed by solving nonlinear potential-based flowmodels. 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.

Automated summary

This study investigates the feasibility of bookings in the European entry-exit gas market and proves that it is coNP-hard when using a nonlinear potential-based flow model. The feasibility of a booking is characterized by computing load flow scenarios with maximum potential difference, which is shown to be NP-hard even with prior knowledge of flow direction. This hardness result distinguishes the easy and hard variants of the booking problem, providing an answer to the general hardness of FB.