7
$\begingroup$

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).

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Nicholas Mancuso
    Jul 4, 2012 at 2:45
  • $\begingroup$ 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. $\endgroup$
    – dysonsfrog
    Jul 4, 2012 at 2:56
  • $\begingroup$ Oops. Brain fart. I see now what you mean. That does sound promising. $\endgroup$
    – dysonsfrog
    Jul 4, 2012 at 3:06
  • $\begingroup$ 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. $\endgroup$
    – Nicholas Mancuso
    Jul 4, 2012 at 3:11
  • $\begingroup$ 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. $\endgroup$
    – dysonsfrog
    Jul 4, 2012 at 3:19

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

You can always use linear programming: just create a variable for each edge and a constraint for each vertex. However there must be a better solution as this does not use the fact that we have a cactus graph. I also suggest to run LP algorithms on a few examples and try to see if anything interesting is happening on cactus graph but not on general graphs.

Improve this answer
$\endgroup$

Your Answer

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

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