Is computing the dual optimum of a degenerate LP equivalent in complexity to solving LP?

Question

Given a primal LP and an optimum solution thereof, it is well-known that complementary slackness conditions [1] can be used in non-degenerate cases to produce a dual optimum solution.

For instance, if we have an LP of the form $\max c^Tx, Ax\le b, x \ge 0$ with $m$ constraints and $n$ variables, and we are given a vertex optimum solution such that at least $m$ primal slack values and primal optimum coordinates are strictly positive, then it is easy to use Gaussian elimination to produce the optimum solution of the dual.

However, many degenerate cases can happen: an optimum vertex can be placed on many more constraints, or many variables can be set to 0, meaning that in such degenerate cases, complementary slackness does not seem to lead to a fast way of getting a dual optimum solution.

Is there an argument showing that the problem of computing any dual solution in such degenerate cases, while knowing the optimum, is equivalent (in complexity) to solving LP from scratch?

Answer 1

Yes, in some sense at least. See the following paper:

Megiddo, Nimrod. "On finding primal-and dual-optimal bases." ORSA Journal on Computing 3.1 (1991): 63-65. PDF available here.

It shows that:

if there exists a strongly polynomial time algorithm that finds a basis which is optimal for both the primal and the dual problems, given an optimal solution for one of the problems, then there exists a strongly polynomial algorithm for the general linear programming problem.

(Note the details of the result though: it is about finding an optimal basis and deals with strongly polynomial-time algorithms.)