Deciding the Feasibility of a Booking in the European Gas Market is coNP-hard

Submission Status:under review
  • 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.
Author:Johannes Thürauf
Document Type:Preprint
Date of Publication (online):2020/05/20
Date of first Publication:2020/05/20
Release Date:2020/05/20
Tag:Potential-based flows, Gas networks, Computational complexity, European entry-exit market, Bookings
Institutes:Friedrich-Alexander-Universität Erlangen-Nürnberg
Licence (German):License LogoCreative Commons - CC BY - Namensnennung 4.0 International