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.
$\begingroup$
$\endgroup$
5
-
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 SuomelaApr 5, 2011 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 SuomelaApr 6, 2011 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 SuomelaApr 6, 2011 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$– user4543Apr 7, 2011 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$– KavehApr 8, 2011 at 8:08
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
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.
-
$\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$– user4543Apr 5, 2011 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$– user4543Apr 5, 2011 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$– 5501Apr 5, 2011 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$– user4543Apr 6, 2011 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$– 5501Apr 6, 2011 at 12:48