Decide whether a point is a vertex of a polytope?

Question

Inspired by the question, I would like to ask the following question:

Input: A polytope specified by $\Theta=\{\vec{x}\mid A\vec{x}\leq b\}$, and its affine projection $f(\Theta)= \{(\vec{c}_1\cdot \vec{x}+ d_1, \cdots, \vec{c}_m\cdot \vec{x}+d_m)\mid A\vec{x}\leq b\}$, a point $\vec{y}\in \mathbf{Q}^m$

Decide whether $\vec{y}$ is a vertex of $f(\Theta)$, what's the complexity?

I strongly believe there is a polynomial time (one might obtain many $\vec{x}$'s which project to the given $\vec{y}$ and check one of these $\vec{x}$'s is a vertex of $\Theta$?). However, I do not have a clear algorithm.

Answer 1

This answer expands on Chandra's comment, and on my follow up comment. The problem is indeed solvable in polynomial time. More general versions of it are also solvable in polynomial time: $\Theta$ could be given by a separation oracle, rather than explicitly, and it is also possible to solve an appropriately formulated version for a polyhedron.

Observe first that we have an efficient separation oracle for $P = f(\Theta) = C\Theta + d$. Indeed, deciding $y \in P$ amounts to solving the feasibility problem $$ y = Cx\\ Ax \le b $$ over the variables $x$. This problem can be solved with the usual techniques, e.g. the ellipsoid method. By the equivalence of separation and optimization, we can also solve arbitrary linear optimization problems over $P$.

Let us first assume $y \in P$: otherwise we are done. Then, by Caratheodory's theorem, $y$ can be written as a convex combination of at most $m+1$ vertices of $P$. Moreover, such a convex combination is computable in polynomial time using a separation/optimization oracle for $P$: this is proved, for example, in Corollary 14.1g of Schrijver's Theory of Linear and Integer Programming. I.e., given an efficient separation oracle for $P$, we can construct a procedure that takes $y$ and returns vertices $v_1, \ldots, v_k$ of $P$, $k \le m+1$, and coefficients, $\lambda_1, \ldots, \lambda_k \in (0,1]$ such that $y = \sum_{i = 1}^k{\lambda_i v_i}$. Then, $y$ is a vertex of $P$ if and only if the procedure returns $v_1 = y$ and $\lambda_1 = 1$. It is clear that if this happens, $y$ is a vertex. Conversely, if this does not happen, then $y$ can be written as a convex combination of other points in $P$, which means that $y$ is not extremal, and, therefore, not a vertex.

Computing $v_1, \ldots, v_k$ and $\lambda_1, \ldots, \lambda_k$ using a separation/optimization oracle is not too hard. First you compute a vertex $u_1$ of $P$: figuring out how to do this by optimizing over $P$ is a nice exercise. If $u_1 = y$, we are done. Otherwise, let $\ell$ be the half-line starting at $u_1$ and going through $y$, and let $z$ be the point where $\ell$ intersects the boundary of $P$. Then $z$ lies in a proper face of $P$, and we can recurse on that face to express $z$ as a convex combination of the vertices of the face. We finish by expressing $y$ as a convex combination of $z$ and $u_1$. See Schrijver's book for the details.