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)
Subscribe to:
Post Comments (Atom)
![[home]](http://people.csail.mit.edu/mip/images/home.gif){kind=small}
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 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.
(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.
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