My problem is as follows: given some LP, we can find an optimal solution for it in (weakly) polynomial time via some interior point method. When there are multiple optima, the found solution might not be an extreme point but on the middle of one of the polyhedrons faces. Now I want to get from there to an optimal extreme point (for example because I have an integral IP formulation and only the extreme points are interesting for me). This should be possible in polynomial time by traversing the current face until hitting some inequality, reducing the dimension of the face by one and repeating until ending on a desired extreme point. Does anyone know a good reference or a text book where this issue is dealt with? So far I could not find a proper resource even though this argument seems to be relevant when making conclusions of the type: "This problem has an ideal and compact formulation and can therefore be solved in polynomial time" asked 09 Feb '15, 09:17 FDahms 
A good starting point is Steven Wright, PrimalDual InteriorPoint Methods, SIAM Press, 1997. There are two steps to converting an interiorpoint solution to a basic solution:
answered 09 Feb '15, 09:39 Matthew Salt... ♦ fbahr ♦ Thank you! 2 is exactly what I needed.
(09 Feb '15, 09:46)
FDahms
Technically, for a proof of polynomial complexity, you really need both steps. The primaldual method terminates close tobut not necessarily onthe optimal face. Megiddo's work assumes that you know precisely a strictly complementary solution, but at termination of the primaldual method, you may have some small but nonzero primal/dual variable pairs that need to be complementary. You need to decide that one or the other of those is the true zero, and choosing incorrectly puts you on the wrong face. Ye's and related work shows how to do that in polynomial time.
(11 Feb '15, 22:39)
Matthew Salt... ♦
