0
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 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$
    – Chandra Chekuri
    May 11 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 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 at 15:52

0

Reset to default

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.