On the Complexity of Recognizing Integrality and Total Dual Integrality of the $\{0,1/2\}$-Closure

Abstract

The $\{0,\frac{1}{2}\}$-closure of a rational polyhedron $\{x:Ax\le b\}$ is obtained by adding all Gomory-Chvátal cuts that can be derived from the linear system $Ax\le b$ using multipliers in $\{0,\frac{1}{2}\}$. We show that deciding whether the $\{0,\frac{1}{2}\}$-closure coincides with the integer hull is strongly NP-hard. A direct consequence of our proof is that, testing whether the linear description of the $\{0,\frac{1}{2}\}$-closure derived from $Ax\le b$ is totally dual integral, is strongly NP-hard.

7 pages