Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard

Abstract

Let $d$ be a positive integer. For a finite set $X\subseteq {\mathbb{R}}^d$, we define its integer cone as the set $\mathsf{IntCone}(X):=\{{\sum }_{x\in X}{\lambda }_x\cdot x\mid {\lambda }_x\in {\mathbb{Z}}_{\ge 0}\}\subseteq {\mathbb{R}}^d$. Goemans and Rothvoss showed that, given two polytopes $\mathcal{P},\mathcal{Q}\subseteq {\mathbb{R}}^d$ with $\mathcal{P}$ being bounded, one can decide whether $\mathsf{IntCone}(\mathcal{P}\cap {\mathbb{Z}}^d)$ intersects $\mathcal{Q}$ in time $\mathsf{enc}(\mathcal{P}{)}^{2^{\mathcal{O}(d)}}\cdot \mathsf{enc}(\mathcal{Q}{)}^{\mathcal{O}(1)}$ [J. ACM 2020], where $\mathsf{enc}(\cdot )$ denotes the number of bits required to encode a polytope through a system of linear inequalities. This result is the cornerstone of their XP algorithm for BIN PACKING parameterized by the number of different item sizes. We complement their result by providing a conditional lower bound. In particular, we prove that, unless the ETH fails, there is no algorithm which, given a bounded polytope $\mathcal{P}\subseteq {\mathbb{R}}^d$ and a point $q\in {\mathbb{Z}}^d$, decides whether $q\in \mathsf{IntCone}(\mathcal{P}\cap {\mathbb{Z}}^d)$ in time $\mathsf{enc}(\mathcal{P},q{)}^{2^{o(d)}}$. Note that this does not rule out the existence of a fixed-parameter tractable algorithm for the problem, but shows that dependence of the running time on the parameter $d$ must be at least doubly-exponential.