About Maximum Independent Set Problem

Tóm tắt báo cáo

Maximum Independent Set Problem asks for a vertex subset in a graph of maximum cardinality such that there is no edge among us.  It is known that the problem is NP-hard in general, i.e. there is no hope about some polynomial time complexity algorithm for solving the problem unless P = NP in general case. In this talk, we will present some up-to-date results, as well as review on some methods for tackling the problem.