I am trying to prove that the problem of having a person at the minimum x number of intersections to be able to see each street is NP-Complete. I think that the street problem is very similar to the Vertex Set problem, and to prove it is NP-Complete I could some form of reduction like 3-SAT to Vertex Set but with my problem in place, to verify the requirement that it is NP-Hard (I can prove it is NP). I'm having an extreme amount of trouble getting started with this however. I've looked many examples of reduction but cannot think how to start my own. How would I show the reduction from 3-SAT to the street problem/Vertex Set?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ This literally is vertex cover. If you require a proof from first principles, then any texbook on complexity theory will contain one; if you don't need a proof from first principles, then the fact that your problem is exactly a famous NP-complete problem is already enough. $\endgroup$– David RicherbyOct 24, 2016 at 14:13
-
$\begingroup$ If you have looked at many examples and still don't have an idea on how to start, I'm not sure we can help you. Our reference question is probably the best you can do, as it highlights some common approaches. $\endgroup$– Raphael ♦Oct 24, 2016 at 15:03
Add a comment
|