# Finding cycle with constraints

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.

• 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, 2011 at 13:25
• It might be helpful if you described your algorithm for cycles of even length. Also, what is the motivation?
– JBL
Apr 4, 2011 at 20:43