<p>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.</p>
<p>We are given a <em>directed</em> graph <span class="math-container">$G$</span> whose edges <span class="math-container">$e$</span> are labeled with numbers <span class="math-container">$x_e \in [0,1]$</span>. We want to check in poly-time whether, for any (directed) cycle <span class="math-container">$C$</span> of <span class="math-container">$G$</span>, we have:</p>
<p><span class="math-container">$$\displaystyle \sum_{e \in C} x_e \leq |C| - 1$$</span></p>
<p>Note that in the integral case (i.e. if <span class="math-container">$x_e \in \{0,1\}$</span>) this can be seen as checking whether the set of chosen edges <span class="math-container">$E' := \{e : x_e = 1\}$</span> contains any cycles.</p>
<p>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 <span class="math-container">$C^*$</span> that maximizes <span class="math-container">$\sum_{e \in C} x_e \ / \ |C|$</span> over all cycles <span class="math-container">$C$</span>, is poly-time solvable, but here we intuitively need to find the cycle <span class="math-container">$C^*$</span> which maximizes <span class="math-container">$\sum_{e \in C} x_e \ / \ (|C| - 1)$</span>.</p>
<p>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.</p>

CC BY-SA 4.0
2022-05-11T20:45:24.357Z
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$.
Chandra Chekuri
CC BY-SA 4.0
2022-05-11T22:53:06.230Z
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!
reservoir
CC BY-SA 4.0
2022-05-17T15:52:51.790Z
@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.
reservoir
<graph-theory><linear-programming><integer-programming>
Separation oracle for breaking cycles in directed graph
reservoir
# Separation oracle for breaking cycles in directed graph

(Asked by: username_0 on 2022-05-11)

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.

**Tags:** graph-theory, linear-programming, integer-programming

> **Comments:**
> **username_1**: 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$.  
> **username_0**: 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!  
> **username_0**: @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.  

---

## 0 answers

