Why is the following true? I cannot understand the intuition behind it.
The weighted maximum independent in a bipartite graph is calculated as follows, connect a dummy source vertex to all left vertices with edge capacity equal to the weights of these nodes in the original graph, do the same with right vertices, and the dummy sink. And for each edge in the original graph, connect the nodes of this edge with infinite capacity in the flow graph. The answer is: (sum of weights of nodes — the maximum flow of this flow graph).
I assume you know why Maximum Independent Set in unweighted bipartite graph is n — max-matching. Now consider an alternate visualization, which will probably make it clear:
Consider we make $$$w_i$$$ copies of node $$$i$$$ (weight $$$w_i$$$). If node $$$u$$$ and $$$v$$$ are connected in the original graph $$$G$$$, assume all copies of $$$u$$$ are connected to all copies of $$$v$$$ in the new graph $$$G'$$$. Finding maximum flow on $$$G$$$ as you described is equivalent to finding max-matching on $$$G'$$$, and you can see Maximum Independent Set on $$$G'$$$ is same as weighted maximum independent set on $$$G$$$.
What if the weights are some irrational number like $$$\pi$$$ or $$$\sqrt{2}$$$? \s
To prove this, we can use Ford-Fulkerson theorem: the maximum flow from $$$s$$$ to $$$t$$$ is equal to the minimum $$$s-t$$$-cut. An $$$s-t$$$ cut is a partition of nodes of the graph into two disjoint sets $$$S$$$ and $$$T$$$ such that every node belongs to exactly one of these two sets, $$$s \in S$$$ and $$$t \in T$$$. The value of the cut is the sum of weights of all edges leading from $$$S$$$ to $$$T$$$.
How to reduce the problem to finding the minimum cut? Suppose we have a fixed cut; let the answer consist of nodes from left part belonging to $$$S$$$ and the nodes of the right part belonging to $$$T$$$.
Suppose we have chosen two adjacent vertices. Then the edge between them contributes to the cut value, so this value is infinite (and since we are trying to find the minimum cut, this won't happen). Each vertex from the left part not belonging to $$$S$$$ is excluded from the answer, and it adds its weight to the value of the cut. The same applies to all vertices from the right part not belonging to $$$T$$$. So, actually, the value of the cut is exactly the sum of weights of nodes we exclude from the answer. That's why the answer is the sum of all weights minus the value of the minimum cut.
In this s-t cut, which nodes will go to s and which will go to t?
the cut works as a barrier, you can use a dfs as long as there is flow to find the nodes.
I mean, to understand what is going on, I need to know which nodes go to s and which node to t. Why is min-cut excluding vertices that are not part of the maximum independent set? This I don't get.
Minimum cut excludes vertices not belonging to the max independent set because it is minimum. You have to maximize the total value of all vertices included in the answer, i. e. minimize the total value of all vertices excluded from the answer — and that is the value of the cut.
To restore the cut itself, you have to make the following: after you have found the maximum flow, run DFS from $$$s$$$ in the residual network. Usually it is used to find a path from $$$s$$$ to $$$t$$$ to push flow through it, but since the flow is maximum, $$$t$$$ won't be reached by this DFS. The cut itself is formed as follows: each vertex reached by this DFS belongs to $$$S$$$, and all other vertices belong to $$$T$$$. After restoring the cut, you can determine which vertices belong to the answer.
Oh, now I get it.
this is related to closure problem / image segmentation, you can read most about this here (section 3)