My PhD research has a negative outcome -- how can I still graduate with it?

Conditions Under-which Fancy Algorithm Has Inflated Error Properties by A. Student. Journal of Science and The Doing Of It. 2017.

This would be a perfectly acceptable paper, and one which should appear in the literature. If you can, correcting said algorithm so it does not do so would be a bonus, but not necessary. Also, it's slightly late for you, but one should always ask when embarking on a thesis/dissertation project "What happens if the answer is "No"?"

Einstein is attributed as saying (paraphrased) "If I knew what I was doing, it wouldn't be called research". I completely agree that a negative result is still a result, and in fact, a very useful one! The other comments address the technical merits, so I will focus on interacting with your advisor.

You have to provide a good pitch. As an academic, he will likely be swayed with good data, so spend some time verifying your result.

• How do you know the algorithm is wrong? Find a way to quantify the error. It might be just comparing it to the well-known case you mentioned.
• Once you have that, run the old experimental data + the new data through your code and make a graph or chart of the error. Show that the original data set results match the original work (so that your code is shown to be correct/consistent implementation of previous work), but that other data sets produce larger error.
• Propose a modification to the algorithm, then re-run all the data. Show that the values and error are still consistent on the original data set, but with lower error on your new data set. Even if its not a real full solution, it's important to show that you have improved it.

For political reasons, you may want to avoid the term "flawed", so as not to insult the past student, but rather to say that you have extended the algorithm to other situations. That's definitely publishable material, as others said.

I think this is doable quickly since it sounds like you already have most of these pieces together, you just need to arrange them to make the argument to your advisor.

I had an old advisor that loved graphs of everything. You could sway him with a good graph. Hopefully that is true for your advisor too. Good luck.

I can't comment on PhD theses, but nobody has mentioned how to actually talk to your advisor.

1. Do not immediately slam your advisor with, "Your favorite students work is wrong, I want to write about how wrong it is."
2. Start by saying that you think (be non-deterministic, there's still a chance you're wrong) you have found some issues with the previous work.
3. Present a clearly written memo detailing the edge cases and why they break the existing work. Include an "out" for the previous student and the advisor. Graciously say that the sample dataset did not include these edge cases so couldn't have been proven broken at the time. Do NOT say that you suspect the previous guy fudged the data.
4. Allow the professor time to digest and draw his own conclusions. (They may have already had suspicions about these edge cases so they may be pretty accepting of this news.)
5. Listen to the feedback. Make a mental distinction of feedback that is their immediate reaction and feedback after "a while".
6. Calmly take in the feedback and spend some time going over to see if it is possible you missed something. Give your rebuttal after "a while". (Don't immediately react to your advisor. You'll say something that you'll kick yourself for later. Your absolute main rebuttal point should be the very first one your advisor hears because people tend to block out the next few arguments while they argue the first one in their head.)
7. After your advisor has accepted that the previous work had flaws, propose the possibility of a paper about why the previous method is incorrect.

This should happen over the course of several days. You both are very good at your technical specialty, but you're both human. This is a social situation and you should approach it as such.