I read the solution from the Codeforces post mentioned in some previous topic
http://codeforces.ru/blog/entry/1797#comment-34342Here I restate it more clearly.
In the graph G, there are n vertices V1, V2, ..., Vn.
Create another graph H which has 2n vertices U1, U2, ..., Un, Un+1, Un+2, ..., Un+n. There are edges (Ui, Uj+n) and (Uj, Ui+n) in H iff there is an edge (Vi, Vj) in G. H is a bipartite graph with L = {U1, U2, ..., Un} and R = {Un+1, Un+2, ..., Un+n}. Find a minimum vertex cover C in H.
For 1 <= i <= n,
if Ui and Ui+n are both in C, assign k to Vi;
if only one of Ui and Ui+n is in C, assign k/2 to Vi;
otherwise, assign 0 to Vi.
Now Vi for 1 <= i <= n are all assigned a value. They are the final answer.
Can someone provide a proof? I don't understand why this solution works at all.
Edited by author 25.11.2016 21:29