A little context: I am implementing a branch and cut algorithm and I have a separation routine, where I construct a digraph and have to run a minimum mean cycle algorithm to check whether some constraint is violated. I know that if the constraint is violated, that then some specific arc $(v,w)$ must be contained in the edge set of the minimum mean cycle.
Now to my question: I have thought about using this structure in some way. At first I implemented Karp's MMC algorithm and was hoping that I could use the fact that I just want to check the mean weight of cycles that contain the edge $(v,w)$. But I was not able to modify the algorithm in such a way that I actually have an asymptotic speed up.
I know that there are other MMC algorithms, that are also faster in practice than Karp's algorithm, but are there algorithms, where modifying them to suit my purpose, imposes a significant speedup?
My constructed graph looks as follows, and I know that the arc which only points into one direction is contained in the MMC, if some constraint is violated.
So far I just compute the MMC in the whole graph without using the information, that the fixed edge must be contained in the cycle.
