I have the following problem: \begin{align}\max&\quad c^T x\\\text{s.t.}&\quad Ax=b\\&\quad x\ge0\end{align}
The matrix $A$ is $m\times n$, where $m<n$.
I have an optimal solution $x^*$ in which all variables are non-zero. I know that there must exist another optimal solution $x^{**}$, a "basic feasible solution", in which at most $m$ variables are non-zero.
Given $x^*$, is there an algorithm for finding $x^{**}$ using polynomially-many arithmetic operations? (I know that $x^{**}$ can be found using the Simplex method, but I am looking for a polynomial-time algorithm).