Semidefinite relaxation for dominating set

ýIt is a well-known fact that finding a minimum dominating set and consequently the domination number of a general graph is an NP-complete problemý. ýIn this paperý, ýwe first model it as a nonlinear binary optimization problem and then extract two closely related semidefinite relaxationsý. ýFor each of these relaxationsý, ýdifferent rounding algorithm is exploited to produce a near-optimal dominating setý. ýFeasibility of the generated solutions and efficiency of the algorithms are analyzed as wellý.