Let $\mathcal G = (\mathcal V, \mathcal A)$ be directed graph with associated edge costs $c_{i,j}$ that has at least one directed cycle.

Define the directed cycle mean cost to be $\frac {\{\text {sum of cost of arcs}\}} { \text {# arcs}}$.

Consider the LP:

$\max \lambda$

s.t: $p_i + \lambda \le p_j + c_{i,j}$ where $(i,j)\in \mathcal A$.

I've shown:

  • The LP is feasible.

  • If $(\lambda,p)$ is a feasible solution then the directed cycle mean cost of every directed cycle is at least $\lambda$.

  • The LP has an optimal solution (doesn't contain a line and $\lambda$ can't be greater than the maximum cost).

Now, I want to show given an optimal solution to the LP, it can be used to construct a directed cycle with minimal directed cycle mean cost.

I really don't have a clue on how to proceed. I don't see how an optimal solution give me the required information ?

  • $\begingroup$ What are pi and pj's? $\endgroup$ Dec 4, 2014 at 11:55
  • $\begingroup$ They are just variables introduced if $(i,j)$ is an edge in the graph. $\endgroup$
    – Shuzheng
    Dec 4, 2014 at 12:03

1 Answer 1


I traced the LP back to this article. Here you can find the answer to your question presented in Theorem 2.

It might be helpful to look at the dual problem of your LP. This is analyzed in the above paper in Theorem 1. In this dual program your variables are defined as variables $z_e\ge 0$ for the edges. Then they show that the optimal cycle is given by the edges for which $z_e>0$ in the optimal solution. Then you can use the complementary slackness condition. It follows that the tight inequalities in your program define the optimal cycle.

Note also that the author provide an interpretation for the variables in your LP. The value of $p_i$ of a vertex not in the optimal cycle denotes the "least length of the path from the vertex $v_i$ to the optimal cycle".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.