(1,2)-HAMILTONIAN COMPLETION ON A MATCHING
Marcin Bieńkowski, Paweł Zalewski · International Journal of Foundations of Computer Science · 2013
We consider the problem of computing a minimum-weight Hamiltonian cycle on an undirected graph with edges' weights from set {0, 1, 2}, where 0-weight edges create a perfect matching of the graph. We provide a (4/3)-approximation algorithm and show that the problem is APX-complete.