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.

  • 1
    $\begingroup$ 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$. $\endgroup$ May 11, 2022 at 20:45
  • $\begingroup$ 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! $\endgroup$
    – reservoir
    May 11, 2022 at 22:53
  • $\begingroup$ @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. $\endgroup$
    – reservoir
    May 17, 2022 at 15:52


Your Answer

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