# Balanced weighting of edges in cactus graph

Given a cactus, we want to weight its edges in such a way that

1. For each vertex, the sum of the weights of edges incident to the vertex is no more than 1.
2. The sum of all edge weights is maximized.

Clearly the answer is no more than $\frac{n}{2}$ for $n$ vertices ($\sum d_i = 2D$ where $d_i$ is the sum for one vertex and $D$ is the sum over every edge). This bound is achievable for cycle graphs by weighting each edge 1/2.

I found a greedy algorithm for trees. Just assign 1 to edges incident to leaves and remove them and their neighbors from the graph in repeated passes. This prunes the cactus down to a bunch of interconnected cycles. At this point I assumed the remaining cycles were not interconnected and weighted each edge 1/2. This got 9/10 test cases but is, of course, incomplete.

So, how might we solve this problem for cacti in general? I would prefer hints to full solutions, but either is fine.

This question involves a problem from an InterviewStreet CompanySprint. I already competed but I'd like some thoughts on a problem (solutions aren't released, and I've been banging my head against the wall over this problem).

• It seems like this should be able to be solved with max flow given capacity constraints of 1 on vertices. You (I) just need to figure how to add a source and sink correctly. Jul 4, 2012 at 2:45
• I thought about that but couldn't find any network that worked. As sxu notes, a good solution almost surely involves the structure of cactus graphs. I'm having a hard time seeing how to use it to build the network. And the fact that I found a solution for trees (at least I think I did; I only sketched a proof for the greedy that I didn't include here) led me away from the LP route. Jul 4, 2012 at 2:56
• Oops. Brain fart. I see now what you mean. That does sound promising. Jul 4, 2012 at 3:06
• My next hunch would be to assign $1/d_i$ where $v_i$ is an articulation vertex (participates in at least 2 separate cycles). Remove $v_i$ and its edges, then rinse and repeat. This should eventually leave you with completely disjoint components. Jul 4, 2012 at 3:11
• Yeah. The nice thing is that with cycles of odd length, you can alternate the weights $1/d_i$, $1 - 1/d_i$, ..., and get around the same $\frac{n}{2}$ bound. That feels good intuitively, but it's still not a full solution. Jul 4, 2012 at 3:19