tag:blogger.com,1999:blog-786333285568106173.post8870532084920475742..comments2024-01-25T01:05:59.968-05:00Comments on WebDiarios de Motocicleta: Cute Problem (I)Mihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-786333285568106173.post-44218411512468599172007-08-22T23:40:00.000-04:002007-08-22T23:40:00.000-04:00Of course :) Thanks Jelani. I got myself confused...Of course :) Thanks Jelani. I got myself confused in the vertex-edge (non)duality.<BR/><BR/>Since cute problems must have elementary implementations, the problem is only interesting when the degree of the tree is bounded.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-7057859325462962912007-08-22T23:30:00.000-04:002007-08-22T23:30:00.000-04:00(spoiler alert -- don't read on if you're actually...(spoiler alert -- don't read on if you're actually thinking about this problem)<BR/><BR/>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 <I>edges</I> 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.<BR/><BR/>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.Jelani Nelsonhttps://www.blogger.com/profile/00216475103758212305noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-90134646117431856312007-08-22T20:10:00.000-04:002007-08-22T20:10:00.000-04:00Yes, the degree of the tree has to be bounded. Dep...Yes, the degree of <B>the tree</B> 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 (<B>parameterized complexity</B> at work).<BR/><BR/>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.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-40213215647829922162007-08-22T17:43:00.000-04:002007-08-22T17:43:00.000-04:00This also reminds me of the following problem:- Gi...This also reminds me of the following problem:<BR/><BR/>- Given a graph and vertex v, find the maximum number of cycles through v, where the cycles are disjoint except for v.<BR/><BR/>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?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-17097334982340295062007-08-22T03:20:00.000-04:002007-08-22T03:20:00.000-04:00Even without the information that Jelani gave, I t...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.<BR/><BR/>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".<BR/><BR/>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().<BR/><BR/>PS, this comment probably makes no sense so I will try to include a <A HREF="http://dblp.uni-trier.de/rec/bibtex/conf/icalp/GargVY93" REL="nofollow"> hint</A>.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-81278797158127739822007-08-21T22:14:00.000-04:002007-08-21T22:14:00.000-04:00I think it's important to say that in the contest ...I think it's important to say that in the contest the max vertex degree was bounded (like, constant).Jelani Nelsonhttps://www.blogger.com/profile/00216475103758212305noreply@blogger.com