Deciding the feasibility of a booking in the European gas market is coNP-hard - Johannes Thürauf (Annals of Operations Research, 2022)
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.
Keywords: 000; Potential-based flows; Gas networks; Computational complexity; European entry-exit market; Bookings