I have a question related to a paper of Chen, Lovasz and Pak [1].

The paper concerns the construction of the Markov chain with optimal mixing time on an arbitrary graph. They prove the optimal bound (conductance bound) can be reached by "lifting" the Markov chain, this comes down to extending the local node features without violating the graph connectivity. The construction of this lift is, as they put it, "closely related to explicity constructing multicommodity flows with minimum congestion".

My first question is: Is the explicit construction of multicommodity flows with minimum congestion NP-hard?

And my second question: In case anyone is familiar with the paper, does the construction of the optimal lifted Markov chain indeed require solving such a multicommodity flow? Otherwise put, is constructing the optimal lifted Markov chain an NP-hard problem? I find the authors to be a bit vague about this.

[1] Chen, Fang, László Lovász, and Igor Pak. "Lifting Markov chains to speed up mixing." Proceedings of the thirty-first annual ACM symposium on Theory of computing. ACM, 1999.

  • $\begingroup$ Thanks for the welcoming and response! Indeed it reads "closely related", so I am guessing that either they don't know how hard the problem is or they want to state that the construction makes explicit use of the solution of an NP-hard problem. By "construction" I mean the Markov chain which is built from the solution of an NP-hard problem. So indeed I figure that I ought to say "...whether this implies constructing the optimal Markov chain will in general be NP-hard." I have corrected this now. $\endgroup$ – smapers Nov 15 '15 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.