Is it possible directly to reduce clique to set cover? I know that there are some ways of direct reduction from Clique to Vertex Cover and from Vertex Cover to Set Cover, so I am very interested to know if the is a way to reduce clique to set cover directly without the use of the transitive rule.

  • 1
    $\begingroup$ Welcome to CS.SE! If you just compose those two reductions that gives you a direct reduction. Have you tried working out what reduction mapping that yields, if you try that? It seems like that immediately gives you what you want. $\endgroup$ – D.W. May 6 '17 at 16:51
  • $\begingroup$ I tried it, but steel can't compouse direct flow, can you please suggest a way how it can be compoused. $\endgroup$ – Erik Feigin May 6 '17 at 20:09

Both problems are NP-complete and, by definition, there is a direct reduction between any pair of NP-complete problems.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.