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 Nelson said...

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

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

Anonymous 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?

Mihai 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 Nelson said...

(spoiler alert -- don't read on if you're actually thinking about this problem)

Your hard instance is a tree of height 1. I'm not sure I understand your hardness reduction right now (an independent set has vertices...what are the edges you're adding to the tree?)...and I'm not sure I will understand it because height 1 trees seem to be solvable by non-bipartite matching (what Dave was alluding to with "FOO()"). The nodes in the graph for matching are the tree's leaves and the edges are the non-tree edges, keeping the same weights.

And as Dave mentioned, for arbitrary height trees it seems this matching approach can be extended in combination with dynamic programming to give a poly-time algorithm (computing the weights in the graph you match in requires solving several dynamic programs). Though in this height>1 case you should think of the nodes in the matching graph as corresponding to edges touching the root and not as corresponding to leaves.

Mihai said...

Of course :) Thanks Jelani. I got myself confused in the vertex-edge (non)duality.

Since cute problems must have elementary implementations, the problem is only interesting when the degree of the tree is bounded.