## Tuesday, August 21, 2007

### Cute Problem (I)

Update: This is a "cute problem" only under the additonal constraint that the degree of the tree T is small (say, lg n). I got myself confused over this when I wrote the post originally. ---

I will post cute problems (mostly from Informatics Olympiads) at random moments in time. Zou can spend a few minutes thinking about them to stay "in shape", or give them as assignments, or just ignore them.

[From IOI'07, which happened last week]
You are given a connected graph G with weights on edges, and a spanning tree T. You must remove a set of edges from G\T, such that no even-length cycle remains in G. Minimize the weight of the removed edges.

Here cycle = a closed walk which doesn't go through any edge or node twice.

Jelani said...

I think it's important to say that in the contest the max vertex degree was bounded (like, constant).

Dave said...

Even without the information that Jelani gave, I think the problem is solvable in n^O(1) time using a subroutine for a "well-known polynomial-time solvable problem" but the subroutine is impractical for anyone to code up from scratch in a short period of time.

This particular subroutine, let me call it FOO(), has been maligned in the past. I think I have seen a theory talk including a testimonial from someone saying "this was the trickiest algorithm I've ever had to code up".

The Waterloo ACM team, in their "book" of code to bring, has a solution to FOO() but only for the uniform-cost version, which is still very tricky. So I'm curious if anyone knows a "nice" solution to FOO().

PS, this comment probably makes no sense so I will try to include a hint.

Dave said...

This also reminds me of the following problem:

- Given a graph and vertex v, find the maximum number of cycles through v, where the cycles are disjoint except for v.

I seemed to think at the time that this could be solved via T-joins. But given that it has such a nice description, is there a simpler solution?

MiP said...

Yes, the degree of the tree has to be bounded. Depending on the audience of the problem it may be better to include this information or not... A mature theory audience would first find an NP-completeness proof for unbounded degree, and then solve the problem with time polynomial in n and exponential in the max degree (parameterized complexity at work).

Reduction: consider a star T with d leaves plus one center. We reduce from maximum independent set on a graph H of d nodes. Simply let G=H union T. An independent set does contain an even cycle (obvious). Now assume you include two edges (u,v) and (u,w). Then there is an even cycle u-v-center-w-u.

jelani said...