# Separation oracle for breaking cycles in directed graph

I am working on a directed graph problem and am collaterally interested to know whether there is a separation oracle for the following set of linear constraints.

We are given a directed graph $$G$$ whose edges $$e$$ are labeled with numbers $$x_e \in [0,1]$$. We want to check in poly-time whether, for any (directed) cycle $$C$$ of $$G$$, we have:

$$\displaystyle \sum_{e \in C} x_e \leq |C| - 1$$

Note that in the integral case (i.e. if $$x_e \in \{0,1\}$$) this can be seen as checking whether the set of chosen edges $$E' := \{e : x_e = 1\}$$ contains any cycles.

These constraints resemble the subtour constraints one knows from TSP or MST relaxations, but I could not use this information/intuition to answer my question. (Mostly because subtour constraints are sufficient, but not necessary to break cycles in the directed case.) Secondly, I am aware that the maximum mean cycle problem, i.e. the problem of finding the cycle $$C^*$$ that maximizes $$\sum_{e \in C} x_e \ / \ |C|$$ over all cycles $$C$$, is poly-time solvable, but here we intuitively need to find the cycle $$C^*$$ which maximizes $$\sum_{e \in C} x_e \ / \ (|C| - 1)$$.

I would not be surprised at all to learn that the answer can be found somewhere on the Internet, but my googling skills have failed me.

• It is same as asking if there is a cycle $C$ such that $\sum_{e \in C} (1-x_e) \ge 1$. This would capture Hamilton Cycle by setting each $x_e = 1-1/n$ for each $e$. May 11 at 20:45
• Oh, I didn't see that! If you want to write an answer I will happily accept it. Do you happen to know if there is a known set of constraints that achieves a similar purpose and is separable? Thank you! May 11 at 22:53
• @ChandraChekuri could you please re-check your argument? The question I meant asking is actually if for all cycles $C$ we have $\sum_{e \in C}(1 - x_e) \geq 1$, which seems to be equivalent to the shortest cycle problem. And this problem is poly-time solvable for non-negative weights. I think the use of the word "any" was unfortunate on my side. May 17 at 15:52