I will answer the following part of the question:
And, explain why. I see some papers assert Degree Constrained Minimum Spanning Tree is an NP-Hard problem and some say it's NP-Complete. Why so?
Some people say “the Degree Constrained Minimum Spanning Tree problem (DCMST) is NP-hard” for a reason, other people say “DCMST is NP-complete” for a different reason.
As is explained in the other answers, the word “NP-complete” means that a problem belongs to NP and is NP-hard. Note that NP is a class of decision problems (that is, problems whose answers are yes/no). Some people avoid saying “DCMST is NP-complete” and choose to say “DCMST is NP-hard” because DCMST is a function problem (that is, not a decision problem) and therefore cannot belong to NP by definition.
However, this is not the end of the story. Other people do say “DCMST is NP-complete.” When they say this, they consider the decision version of the problem implicitly:
- The function version of DCMST: Given a graph G with edge weights and a positive integer d, find a minimum-weight spanning tree of G whose maximum degree is at most d.
- The decision version of DCMST: Given a graph G with edge weights and positive integers d and k, decide whether G has a spanning tree whose maximum degree is at most d and whose total weight is at most k.
Therefore, if you accept the convention to refer to the decision version as DCMST, it is perfectly fine to say that DCMST is NP-complete. In computational complexity theory, this convention is often used.
Note that the decision version of DCMST can be solved in polynomial time if and only if the function version of DCMST can be (“if” is easy, “only if” is slightly more difficult). This is why calling the function version and the decision version by the same name causes little confusion.