2
$\begingroup$

Given a graph in which each vertex $A_i$ has float value $B(i)$ between 0 and 1 inclusive. How can we find a cycle (if such exists) with vertices $[C_1, C_2, ..., C_k]$ which violates following condition: $\sum(B(C_i)]) \le k/2$ (integer division)? Thank you.

$\endgroup$
  • 3
    $\begingroup$ This seems to be very closely related to the problem of finding a cycle of minimum average weight. See, for example, these lecture notes. In your problem you have weights on nodes while the usual formulation has weights on edges, but I believe similar techniques can be applied. $\endgroup$ – Jukka Suomela Apr 5 '11 at 12:03
  • $\begingroup$ For the case of an odd $k$, it might be easier to consider the following formulation: given a node-weighted graph, find an odd cycle $C$ that maximises $(w(C) + 1)/\ell(C)$, where $w(C)$ is the total weight of $C$ and $\ell(C)$ is the length of $C$. $\endgroup$ – Jukka Suomela Apr 6 '11 at 19:08
  • 1
    $\begingroup$ In any case, this is such a strange-looking problem that it would be nice if you gave some background information: why are you interested in solving this problem? $\endgroup$ – Jukka Suomela Apr 6 '11 at 19:09
  • $\begingroup$ This problem was asked by my friend. And it is interesting for me, how to efficiently solve it, especially for the odd cycles. $\endgroup$ – user4543 Apr 7 '11 at 15:35
  • $\begingroup$ Agree with Jukka, it would be nice to know why your friend is interested in the question. :) Can you ask him/her and add it as a motivation to your post? $\endgroup$ – Kaveh Apr 8 '11 at 8:08
3
$\begingroup$

I assume that your graph is undirected.

If you allow $k/2$ without integer division, then you can reduce your problem to computing the maximum mean weight cycle. Replace every undirected edge by two directed egdes. Every edge leaving a node $A_i$ gets value $B(i)$. Compute a cycle of maximum mean weight (i.e., with maximum average edge weight). You condition is violated if and only if the maxium mean weight is $> 1/2$.

The maximum mean weight cycle as well as the minimum mean weight cycle can be computed in polynomial time by Karp's algorithm, see Cormen, Leiserson, Rivest, Stein.

If you insist on integer division, things get more delicate, since there could be several maximum mean weight cycles and a longer one can satisfy the bound but a shorter one need not. You can slightly reduce the weights (by a constant $\epsilon$ which is negligble compared to your edge weights). This will favour shorter cycles and you might get away with this.

$\endgroup$
  • $\begingroup$ Thanks for the response. I have found solution for the even-length cycles (just find negative-weight cycle in the reduced graph). But it doesn't work with odd-length. $\endgroup$ – user4543 Apr 5 '11 at 15:34
  • $\begingroup$ How can we reduce the edges? This 3-length cycle with weights [0.334, 0.333, 0.334] violates the constartint, so we should catch it. So, if we reduce it by 0.001, it becomes ok. $\endgroup$ – user4543 Apr 5 '11 at 15:58
  • $\begingroup$ Assume that your weights have a maximum of $s$ decimal digits. Then the smallest possible violation is $10^{-s}/n$. Now decrease all edge weights by $10^{-s-1}/n^2$. If there was a violation before, then there will be a violation afterwards, too. $\endgroup$ – 5501 Apr 5 '11 at 19:01
  • $\begingroup$ Suppose, we have 6-length cycle with mean = 0.5 (sum is 3) and 9-length cycle with mean = 0.5 (sum is 4.5). 9-length cycle is violated constraint (cause 4.5 > 9 / 2 = 4). How can we handle this case? $\endgroup$ – user4543 Apr 6 '11 at 12:11
  • $\begingroup$ That's indeed a problem. Reducing the weights only works if the minimum mean weight cycle with the fewest edges is odd. Sorry, I overlooked this... $\endgroup$ – 5501 Apr 6 '11 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy