Homework 3
October 22nd, 2007Homework 3 is now online (pdf, latex). Remember that it is due next Monday, Oct 29.
Some comments:
- In the second problem, you are asked to show that heuristics for a poly-time solvable problem yield 2-approximations. It is not only NP-Complete problems that need approximations. Often, a problem can be solved exactly in polynomial time, but an approximation can be found much faster, and depending on the application, this might be acceptable.
- The final problem is a canonical example of how to prove that the planar version of a problem is NP-Complete: You take the problem, lay it out on the plane, and find some gadget that removes crossings while preserving whatever measure you’re trying to compute. Solving this problem will give you a good idea of how to attack any problem of this kind. A warning though: this problem will take some time, so don’t expect to be able to solve it on Sunday night without spending some time before then !
Update: I’ve extended the assignment deadline to Oct 31, Wednesday, at 5pm.
Entries
October 23rd, 2007 at 2:01 pm
On 3.3, the crossing-gadget claims to add 18 vertexes. And this seems true, however when there are several gadgets (figure 3.3), each one adds 22 vertexes. Should it be the case that figure 3.2 actually has 4 more nodes? (The original v1, v2, u1, u2, which would connect to what the figure currently calls v1, v2, u1, u2, respectively.)
October 23rd, 2007 at 2:19 pm
Hmm. I was wondering about that as well when I drew the gadget out. I think that for consistency you should assume that the 4 extra nodes are added in as well, in the first figure.
October 24th, 2007 at 7:07 am
In 3.1.2(LONGEST PATH problem), does the definition of a path allow cycles in it?
October 24th, 2007 at 9:20 am
No, a path does not contain cycles. Technically, at least in some graph theory books, a path does not overlap vertices, a circuit does not overlap edges, and a walk can do anything, but I don’t know how consistently that rule is applied.
For the purpose of this problem, a path is a tree where each vertex has degree at most 2
October 25th, 2007 at 1:47 pm
On 3.5, just to be sure…
The idea is that we replace every /required/ crossing with a gadget, right?
If I have a planar graph, there may be ways to draw it such that there are crosses. But the idea is that we can detect was edges /must/ cross (or, at least, how many crossings there have to be), and we do this gadget voodoo on those, right?
October 25th, 2007 at 1:56 pm
Yes. A separate problem on graph drawing is to draw a graph in such a way as to minimize crossings. We are not worried about that. MOre formally, assume that you are given two polynomial time procedures that do the following:
1. A poly-time procedure that takes a graph and decides whether it is planar or not
2. A polytime procedure that draws a graph on the plane (without regard to crossings). and provides coordinates for all vertices, and even (if you like) a list of pairs of edges that cross (although these last thing can be gleaned from the coordinates in polytime)
In short, assume anything you need to in order to get to a drawing of the graph on the plane (maybe with crossings) with any additional info you need. AS LONG AS it’s polytime doable.
So your reduction will start something like:
1. Run procedure 1. If the graph is planar, pass it on as is
2. If not, run procedure 2 and obtain a drawing with whatever info you need
3. Now start the gadget magic.
October 29th, 2007 at 1:54 am
Question 5 just asks us to prove NP-Hard. I thought that we don’t have to prove the NP part …
October 29th, 2007 at 10:06 am
Well, the NP part follows from the fact that VERTEX COVER is in NP, so I didn’t think it was necessary.