0
$\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 $[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.

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ But it works only for the even-length cycles. $\endgroup$
    – Anton
    Apr 7, 2011 at 8:57
  • $\begingroup$ Is it possible to add a vertex on every edge, with appropriate weight? Each cycle will then be even... $\endgroup$ Apr 7, 2011 at 13:37
  • $\begingroup$ 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... $\endgroup$
    – Anton
    Apr 7, 2011 at 15:34
  • $\begingroup$ 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. $\endgroup$
    – Orange
    Apr 7, 2011 at 22:25
  • $\begingroup$ 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! $\endgroup$
    – Orange
    Apr 7, 2011 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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