In order to overcome the defect of attribute reduction based on discernibility matrix in the theoretical research of rough sets, an attribute reduction algorithm based on the power graph is proposed. The inconsistent decision tables are converted into consistent decision tables by altering the value of decision attribute. Combined with the concept of the sample pair and power graph, the attribute reduction of inconsistent decision table based on the revised discernibility matrix is translated into the searching problem in power graph. Finally, the example and experiment show the effectiveness of the proposed algorithm.