SetCover

Textbooks:
Computational Complexity: A Modern Approach by S. Arora and B. Barak.
Algorithm Design by J. Kleinberg and E. Tardos.
Lecture slides by K. Wayne accompanying the latter textbook:
www.cs.princet...

[@MohdYaseenmas]

Thank you

[@user-rf4ue5kc3u]

thank you so so so so much!!! you explain everything so clearly!!!!

[@pasc4le]

Is the reduction possible when the elements of U appear more (or less) than twice in the collection of subsets? And if yes, how?

[@tarvos_trigaranvs]

I was thinking about the same, but no, so only the vertex cover reduces to the set cover problem this way. But you can reduce the set cover to vertex cover in a different way too.

[@NS-bi8bi]

Thank you so much!

[@yaras9648]

If K = 3 or generally > 2, can you still find a solution in polynomial time?

[@motivationalcomred]

do independent reduces set cover ? when independent set reduces vertex cover and vertex cover reduces set cover do transition property hold here logically it works i know if u could map input of vertex cover as set cover you can map it with negation(independent set ) too . my q is the transition property holds or not in general

[@Red_Devil_-es1rt]

afaik Transitivity does hold with carp reductions. So if x

[@Red_Devil_-es1rt]

this could be thought of rather trivially by applying the carp reduction function from x to y (let's call it f) then applying the carp reduction function from y to z (let's call it g).
So our new reduction function would be h(x) = g(f(x))

[@compscilessons]

Thank you! Yes, we do have transitivity for polynomial-time Karp reductions. There is some further discussion in this related video: ua-cam.com/video/eAIiBIzfWaU/v-deo.html

[@rajukachori9536]

CAN U EXPALIN HOW U TOOK K=2 AND WHAT IS K

[@Muhammad_Huzaifa_Shahab]

Same issue