patternMinor
Balanced weighting of edges in cactus graph
Viewed 0 times
cactusedgesweightinggraphbalanced
Problem
Given a cactus, we want to weight its edges in such a way that
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).
- For each vertex, the sum of the weights of edges incident to the vertex is no more than 1.
- 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).
Solution
So this question has been bothering me: why a cactus, if there's already a linear-time algorithm for a more general class?
The primal problem is known as the fractional matching problem, and, unsurprisingly, it has been studied as well. Balinski (whose result was made known to me via Schrijver's book Combinatorial Optimization) characterized the extreme points of the fractional matching polytope as consisting of an integer matching plus half of a collection of odd cycles. Given the relatively low input limits, I suspect that the intended solution of the problem poser was to modify Edmonds's blossom algorithm in a way that, for now, I will leave for you to discover. The structure of the cycles in a cactus makes this algorithm simple enough to be appropriate for a contest.
As sxu points out, this problem is amenable to linear programming. If you need just the objective value, the dual LP has the same objective value and is the fractional vertex cover problem. The nice thing about vertex cover is that it has a half-integral optimum; in linear time, you can use depth-first search to compute a tree decomposition of the cactus of width O(1) and solve the dual LP with a dynamic program that tries variable values in {0, 1/2, 1}.
If you actually need a solution for the primal, then complementary slackness might help, but I can't help but suspect that the restriction to cacti is supposed to allow a more elementary solution.
The primal problem is known as the fractional matching problem, and, unsurprisingly, it has been studied as well. Balinski (whose result was made known to me via Schrijver's book Combinatorial Optimization) characterized the extreme points of the fractional matching polytope as consisting of an integer matching plus half of a collection of odd cycles. Given the relatively low input limits, I suspect that the intended solution of the problem poser was to modify Edmonds's blossom algorithm in a way that, for now, I will leave for you to discover. The structure of the cycles in a cactus makes this algorithm simple enough to be appropriate for a contest.
As sxu points out, this problem is amenable to linear programming. If you need just the objective value, the dual LP has the same objective value and is the fractional vertex cover problem. The nice thing about vertex cover is that it has a half-integral optimum; in linear time, you can use depth-first search to compute a tree decomposition of the cactus of width O(1) and solve the dual LP with a dynamic program that tries variable values in {0, 1/2, 1}.
If you actually need a solution for the primal, then complementary slackness might help, but I can't help but suspect that the restriction to cacti is supposed to allow a more elementary solution.
Context
StackExchange Computer Science Q#2598, answer score: 5
Revisions (0)
No revisions yet.