Questions That Don't Deserve Their Own Blog — I guess it'd be good to have something like this as a place to ask random questions about problems ("I accidentally my code, wat do?") without having your blog post get downvotebombed?
I have a question about Yandex.Algorithm 2015 round 2.2E: the problem can be reduced to computing the min. bipartite vertex cover that can't fully cover one side and since the dual of min. vertex cover is max. matching, I tried to find the dual of this problem.
I mean, that vertex cover can be described as a linear programming problem
- xi ≥ 0
- xuj + xvj ≥ 1 for each edge ej = (uj - vj), 1 ≤ j ≤ E
Its dual should be
- for 1 ≤ i ≤ N, (sum over edges incident on vertex i in the left part)
- for N + 1 ≤ i ≤ N + M, (same as above for the right part)
yj are variables assigned to edges (flow through them); are assigned to the left and right part of the graph and if they're fixed, finding the optimal yj is just bipartite matching/flow. However, this gives the optimal solution as for example for an almost complete bipartite graph KN, N that's missing just one edge, which doesn't make sense.
What am I missing here?