MSP Problem: Its NP-Completeness and Its Algorithm
Xinwen Jiang, Lihong Peng, Qi Wang · 2010
In this paper, we propose a problem named as MSP, prove its NP-completeness, and design an algorithm to solve it. To prove the algorithm, we define a linear order to align all the instances of the problem, and also define a so-called splitting transform to get a smaller graph. Using the linear order, we prove the non-existence of the smallest graph which makes our algorithm failed by performing splitting transform on the smallest graph to obtain a smaller graph. It seems that our algorithm is a polynomial one. So we would like to discuss it with more people. This paper is the summarization of.