Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 $[A_1, A_2, ..., A_k]$ where $\sum(B_i) \le k/2$ (integer division)?

I produced an algorithm for the even-length cycle. But how to manage solution for the odd?

Thank you. P.S. It is not a homework problem.

share|improve this question
    
Please edit for typos and LaTeX. Such a cycle obviously need not exist -- what is the actual question you intend? Is this a homework assignment? –  JBL Apr 4 '11 at 13:25
1  
It might be helpful if you described your algorithm for cycles of even length. Also, what is the motivation? –  JBL Apr 4 '11 at 20:43
add comment

1 Answer

It all became clear after an hour of thought. Here is what you do. To edge ij you assign the weight .5(B_i+B_j)-.5. If there is a cycle of length k, since each vertex is entered once and left once, the sum of the weights of these edges is the sum of the float values of the vertices-k/2. So you are searching for a cycle with weight at most 0, essentially a negative cycle. How do you do this? Well since you have negative weights, you must use Bellman-Ford rather then Dijkstra, but Bellman-Ford can identify negative cycles (and 0 weight cycles)! So look up Bellman-Ford. You may also find the philosophy of problem 7 in this midterm's solutions https://hkn.eecs.berkeley.edu/files/exam/CS170_fa04_mt1_sol.pdf to be useful. Thanks for the nice problem.

share|improve this answer
    
But it works only for the even-length cycles. –  Anton Apr 7 '11 at 8:57
    
Is it possible to add a vertex on every edge, with appropriate weight? Each cycle will then be even... –  Per Alexandersson Apr 7 '11 at 13:37
    
Main problem is to determine the weights of added edges. Anyone know how to add them. There are many approaches for the even-length cycles, but for odd... –  Anton Apr 7 '11 at 15:34
    
I am still bewildered by your claim that it only works for even cycles, but if you insist that this is the case, then as Paxinum suggests, add a vertex v_ij on each edge ij, then the weight for the edge connecting i and ij is .5B_i-.25 and the weight for the edge connecting ij and j is .5B_j-.25 and everything is working as above. –  Orange Apr 7 '11 at 22:25
    
Oh and of course if you do take Paxinum's approach, after adding this vertex v_ij and the edges with weights that I suggest, you ought to remove the original edge ij! –  Orange Apr 7 '11 at 22:30
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.