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?
Is computing the dual optimum of a degenerate LP equivalent in complexity to solving LP?
optimization;linear programming