Polynomial time certifying algorithms for the planar quantified integer programming problem

摘要

This article is concerned with the design and analysis of polynomial time algorithms for determining whether a Planar Quantified Integer Program (PQIP) is feasible. A PQIP can be described briefly as an integer program involving two variables, in which each variable can be either universally or existentially quantified. There are four types of PQIPs, depending on how the variables are quantified (existentially or universally). In this article, we present two new, simple, and efficient algorithms for the V3 case as well as a detailed account of the complexity of the other cases. Moreover, we discuss certification with respect to the provided algorithms.