Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

4
  • 3
    $\begingroup$ Welcome to CS.SE! Have you tried to prove your algorithm correct? Have you tried running it on millions of randomly generated graphs, and comparing its output to a brute-force algorithm that is known to be correct, to search for counterexamples? Vertex Cover is NP-hard, so if your algorithm is correct, it would imply P=NP, which would amount to a major breakthrough. It isn't our purpose on this site to try to make major breakthroughs or review claims of major breakthroughs, such as a claim to have proven that P=NP. Personally, I doubt the algorithm is correct. $\endgroup$ Commented Apr 26, 2017 at 1:11
  • $\begingroup$ I also doubt the algorithm is correct, but I don't know how to prove that it is. NP-hard and NP-complete problems are so complex that, to my knowledge, there isn't a way. I like your idea of following up with randomly generated graphs but I can see two major problems: 1) if it works for those graphs, how do I prove that it works for all graphs or is better than the current approximation algorithm? 2) How would I know that testing against graphs is complete (RE: Decidable TMs). Thanks for your input, I'll keep looking into this. $\endgroup$ Commented Apr 26, 2017 at 1:38
  • 4
    $\begingroup$ I'm voting to close this question as off-topic because it is a request to verify what would amount to a major breakthrough in theoretical computer science. $\endgroup$ Commented Apr 26, 2017 at 7:03
  • 3
    $\begingroup$ Looks like the algorithm is easy to implement. Do that and run it on small examples and compare with optimal solutions you get with say brute force. $\endgroup$ Commented Apr 26, 2017 at 9:14