The Negative Cycles Polyhedron and Hardness of Testing Polyhedral Properties

$w:E\mapsto\RR$, we consider the polyhedron $P(G,w)$ of negative-weight flows on $G$, and get a complete characterization of the vertices and extreme directions of $P(G,w)$. For any CNF formula $\phi$, we give a construction mapping $\phi$ into a weighted graph $(G(\phi),w)$ such that the existence of a negative-weight cycle of length greater than 2 in $G$ is equivalent to the satisfiability of $\phi$.

We use this characterization and construction to show that the following problems are NP-hard:

(i) generating all vertices of a $0/1$-polyhedron;
(ii) checking if a given integral polyhedron is $0/1$, or if a given
polyhedron is half-integral;
(iii) approximating the maximum support of a vertex in a polyhedron in
$\Re^n$ to within a factor of $\Omega(1/n)$;
(iv) approximating the vertex centroid (which the average of the vertices) of a given polyhedron in $\Re^n$ to within a distance of $n^{1/2-\delta}$ for any fixed $\delta>0$.