How to write critique in a paper? As part of the introduction of a paper I want to write some critique on previous research which was published at some reputable conference. It basically amounts to their research methodology being invalid. Their results are useless, because they did some things which basically amounts to cheating their scores. However they claim to be state-of-the-art. Now it takes a couple of paragraphs to explain what was all wrong with their work, which might clutter the introduction. The audience of the paper may not be familiar with the reason. My intention of the paper is to present something with a correct methodology.

The main point is: if you have some critique on related work, how do you include this in the paper? How polite should you be about the previous work?
First of all, I do not like the tone of your question (no offense). It seems like you are having a personal vendetta with those authors, which is a) silly b) unjustified (they did not anything to harm you personally) c) counterproductive for your purpose of publishing your work.

Let's summarize some facts:


  However they claim to be state-of-the-art


Either they are or they are not. If this paper is not the state-of-the-art, you should compare your work against the "true" state-of-the-art. If they are considered the state-of-the-art by the community, you should acknowledge that fact. In fact, if this paper has obvious disadvantages, this is even better for you, since it will be easier to show why your approach is better.


  they did some things which basically amounts to cheating their scores


You are probably exaggerating. Some kind of overselling results is normal, but you are implying malpractice, which is not that common. So, tone it down and try to express a cold, neutral and objective evaluation of the other paper, with lots of arguments and experiments that back your opinion in your paper. Also, when you are objective and not trying to trash the other paper, reviewers will buy more into your argumentation. Also, consider that the authors of this paper might also be: a) your future reviewers b) your future collaborators c) your future employers. So, treat your "opposition" with respect. This makes it easier for them to treat you with the same respect and more easily acknowledge and digest the fact that your method is better and their method is worst (they are after all a part of the same community), which makes future collaborations easier and improves your visibility.   


  As part of the introduction of a paper I want to write some critique
  on previous research


Critique is not a motivation. You should first discuss the problem, why it is important, very briefly what previous methods have done on this problem and then you say very briefly and in a very neutral way the shortcomings of previous methods (not just this one paper but all that have come before) and why your work will be better. Then you slightly augment this argumentation in the related work section (about their shortcomings) again neutrally. It is your experiments section that needs to truly show why your method is better and how much better it performs, only after very thorough and exhaustive experiments that will overcome every reviewers' doubts.

TL;DR. Keep your critique short, neutral and objective. There is not need to be humble about the advantages of your method but that does not need to be by trashing previous works.