hw hint

[Jared Saia]

A hint on problem 3 of the hw.

Note that for all the network flow algorithms we discussed in class (Fat-Pipe, Short-Pipe, Ford-Fulkerson), the following is true:

- If the capacities of all edges are integers, then all flow values returned in the max flow are integers.  

This is true since each augmenting path will increase flow by an integral value.  This is sometimes called the Integrality Invariant.

Jared

[Stephen Harding]

Professor Saia,

Are we required to use the hint in problem 3? I think I found a way to prove it without relying on the Max flow/Min Cut Theorem.

Thanks!

Stephen

Jared

--
 
 

[Jared Saia]

Stephen,

I'd prefer if you solve this problem using the Max flow/Min Cut theorem.  Among other things, if you do it that way, it'll help you on a related problem that may appear on the final.

Jared

p.s. There are certainly other ways to show this result, but I don't think any of them are any easier then using the Max flow/Min Cut theorem.

--
 
 

[Stephen Harding]

OK, will do.

Out of curiosity, does my old solution look right to you? (see attached)

Thanks,

Stephen

--
 
 

[Jared Saia]

Stephen,

There's a problem in the following:

"(if a then b) is logically equivalent to (if not b then not a)"

- Ok so far

"Thus, it is sufficient (equivalent) to prove that If |N(S)| < |S| then there is not perfect matching in G."

- This is a mistake.   You've mismatched the statements a and b.  a is the statement "For all S, |N(S)| >= |S|".   b is the statement "There is a perfect matching"

Thus, "if not b, then not a" is equivalent to

"If there is no perfect matching, then there is some subset S such that |N(S)| < |S|"

This is a much harder statement to prove.  Again the Max-flow/Min-cut Theorem leads to the simplest proof I know for this problem.

Hope this helps!

Jared

--