1
$\begingroup$

I want to show that shortest acyclic orientation(SAO) is NP complete.Since vertex cover in Np complete so if vertex cover is reduced to shortest acyclic orientation then it will also be NP complete.

SAO take input a graph G and integer k and answers if G has acyclic orientation with no directed k+1 path.

$\endgroup$
  • $\begingroup$ shortest acyclic orientation problem takes input a Graph G and an integer K and answer the question ' Does G have acyclic orientation with no directed (k+1) vertex path. $\endgroup$ – shakir Apr 19 '15 at 11:14
  • $\begingroup$ because vertex cover problem is NP complete...so if I reduce my problem to vertex cover problem then it would also be NP complete $\endgroup$ – shakir Apr 19 '15 at 11:16
  • 1
    $\begingroup$ OK, I see you have the reduction the right way around, now. I make that mistake all the time! But why specifically vertex cover? If your goal is to prove NP-completeness, it's enough to reduce any NP-complete problem to SAO. What did you try? Where did you get stuck? $\endgroup$ – David Richerby Apr 19 '15 at 13:01

Your Answer

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

Browse other questions tagged or ask your own question.