Add 4 auxiliary nodes s',a,b and t' and split any existing node v[i] to v1[i], v2[i]. If there's an edge from v[i] to v[j], there would be an edge from v2[i] to v1[j] with capacity 1. The edges s'->s, t->t', a->any v2[i], any v1[i]->b, any v1[i]->v2[i] have infinity capacity. s'->a and b->t' has a capacity of k. All edges are directed.
Lemma 1: a unit flow s'-a-...-b-t' result in deleting some(at least 1) edges in the original graph. This is quite obvious because this flow must take the capacity of some original edge. Lemma 2: There exists a maximum flow in new graph G' that s'->a is full. This is because deleting any edge from the original graph will at most cause the maximum flow to decrease by 1, by increasing the flow from s'->a we can increase the maximum flow by 1. Lemma 3: There exists a maximum flow in new graph G' which is correspondent to delete only k edges. This is because deleting more edges obviously decrease the maximum flow. So the smallest s-t flow in G is the maximum flow in G'-k. Some more efforts are required to really construct the flow.... I didn't think very clearly about that, maybe we can find a flow which s'->a and b->t' is full first and then try to find augumenting-path without using s'->a or b->t'. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
