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.

## Tuesday, August 21, 2007

### Cute Problem (I)

Posted by Mihai at 8:55 PM

Subscribe to:
Post Comments (Atom)

## 6 comments:

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

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.

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?

Yes, the degree of

the treehas 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 complexityat 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.

(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

edgesyou'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.

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.

Post a Comment