Why can't set cover be reduced to min-cost max-flow? Okay, so I know obviously I'm making some kind of easy mistake here, since set cover is NP-complete and min-cost max-flow is in P, but I can't figure out what the mistake is.
So, given a universe $U$ and a set $S$ such that the union of all sets in $S$ is $U$, the set cover problem asks for the smallest subset of $S$ such that the union of all sets in that subset is $U$.
My question, then, is why we can't construct a min-cost max-flow graph as follows:


*

*Create one node for each set in $S$, and one node for each element in $U$.

*Draw edges from the source to each set $A \in S$ with 1 cost and infinite capacity.

*Draw edges from each element in $U$ to the sink with 0 cost and unit capacity.

*Draw edges from each set in $S$ to each of the elements in $U$ that it contains with 0 cost and infinite capacity.

*Find the min-cost max-flow of the resulting network; the sets $A \in S$ that have flow running through them should comprise a set cover.


Wikipedia provides an example problem with $U = \{1, 2, 3 ,4, 5\}$ and $S = \{ \{1, 2, 3\}, \{2, 4\}, \{3, 4\}, \{4, 5\} \}$ -- here is a picture I drew to illustrate. 
The resulting graph will have $|S| + |U| + 2$ nodes, and $\Sigma_{A \in S} |A|+ |S| + |U| + 2$ edges, which I believe should be polynomial on the size of the input. So what am I doing wrong here? Thanks!

To put it simply: your algorithm only guarantees to fill every node in the last(right) layer but it is not restricted anywhere on the number of subsets it uses from the first(left) layer. For example in the wikipedia case you mention it could use $\{1,2,3\}$ for the $1$, $\{2,4\}$ for the $4$ and $\{4,5\}$ for the $5$. Of course the $2$ can and should be obtained from the first set but this information is never encoded in the flow construction and that is the issue. 
