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 $[C_1, C_2, ..., C_k]$ which violates following condition: $\sum(B(C_i)]) \le k/2$ (integer division)?
Thank you.
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 $&gt; 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.