reduction in review session

9 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.

Jared


Reply all
Reply to author
Forward
0 new messages