reduction in review session

10 views

Skip to first unread message

Jared Saia

unread,

Dec 11, 2012, 6:54:15 PM12/11/12

to cs561-f12

A couple things:

- I wanted to remind people that the reduction we talked about at the review session is harder than the reduction problem I will ask in the problem

- In the review session, I left out the argument that G' has a MTFS of size n+k iff G has a Indep. Set of size k. In a real reduction, you'd need to include this argument.

- There are many examples of reductions in the lecture slides. If you're confused about how to do them, please go through these carefully.