A couple of small clarifications on problem 1a (I hate to be pedantic, but I think they make a difference :-):
1) Is an edge critical if *some* decrease in its capacity (say decreasing it to 0) would decrease the max flow, or if *any* decrease in its capacity would decrease the max flow?
2) Is the if in the definition an iff?
3) It looks like we only need to give an efficient algorithm that finds *a* critical edge (not necessarily all of them). Is that right?
I don’t quite understand what the question 2(b) is asking for.
Does it mean that: 2(a) indicates the vertex cover of a biparti-graph is a P problem, while the vertex cover of general graphs is an NP problem, and therefore P~=NP ?
Problem 4.4 (7.17 from K&T) says the algorithm should figure out which nodes had been deleted in O(k log n) pings. What is n? I’m guessing n = |V| but that is never stated in the problem.
In question (4), is the structure of the graph G supposed to be unknown? Otherwise, one can just run the Fulkson algorithm to find the min cut, and hence identify all reachable nodes.
In other words, the problem can be stated as: given a graph without knowing its structure (i.e., V is known but E is unknown), give an algorithm to identify all nodes in the s-side of its min-st-cut? Am I correct?
Another clarification needed for question 1(b). Is the current flow a max-flow or an arbitrary flow? If it’s a max-flow, should the updated flow still be a max-flow in the new graph( in which one edge changed the capacity)?
This goes back to my comment to Dafang: imagine that the original structure is known to you, and so you *do* have augmenting paths. the problem now is that something is wrong with the picture of the network, and you have to troubleshoot
In question 5, when we say “augment a graph M with an augmenting path P’, does it mean that the updated graph is M’ = M \delta P, and |M’| = |M|+1? This is inferred from the information given by the mid-exam.
Well I mean, run one step of FF using this path P. So yes, it means what you say, but that can be inferred independently of the midterm (I don’t want you all scrambling off to look at it :))
Entries
November 7th, 2008 at 8:24 pm
A couple of small clarifications on problem 1a (I hate to be pedantic, but I think they make a difference :-):
1) Is an edge critical if *some* decrease in its capacity (say decreasing it to 0) would decrease the max flow, or if *any* decrease in its capacity would decrease the max flow?
2) Is the if in the definition an iff?
3) It looks like we only need to give an efficient algorithm that finds *a* critical edge (not necessarily all of them). Is that right?
Thanks.
November 7th, 2008 at 9:32 pm
1. An edge is critical if you can decrease its flow by 1 unit and decrease the max flow. how’s that ?
2. Not iff (that would imply that there’s only one critical edge in a graph). Just if
3. Correct. Find *some* critical edge.
November 8th, 2008 at 1:37 am
I don’t quite understand what the question 2(b) is asking for.
Does it mean that: 2(a) indicates the vertex cover of a biparti-graph is a P problem, while the vertex cover of general graphs is an NP problem, and therefore P~=NP ?
November 8th, 2008 at 1:39 am
I think the question is quite clear. it’s possible that you’re confused because you think it’s harder than it is
November 8th, 2008 at 5:45 pm
Problem 4.4 (7.17 from K&T) says the algorithm should figure out which nodes had been deleted in O(k log n) pings. What is n? I’m guessing n = |V| but that is never stated in the problem.
November 8th, 2008 at 5:47 pm
Yes. n = |V|
November 9th, 2008 at 12:04 am
In question (5), what does m and n stand for? I guess they’re the number of vertices and edges, but just to make it clear
November 9th, 2008 at 12:14 am
m = #edges, n = #vertices.
November 9th, 2008 at 12:52 am
In question (4), is the structure of the graph G supposed to be unknown? Otherwise, one can just run the Fulkson algorithm to find the min cut, and hence identify all reachable nodes.
In other words, the problem can be stated as: given a graph without knowing its structure (i.e., V is known but E is unknown), give an algorithm to identify all nodes in the s-side of its min-st-cut? Am I correct?
November 9th, 2008 at 1:30 am
Well the structure of G is known at first. But then edges get sabotaged, and you need to find which ones.
November 9th, 2008 at 2:51 am
Another clarification needed for question 1(b). Is the current flow a max-flow or an arbitrary flow? If it’s a max-flow, should the updated flow still be a max-flow in the new graph( in which one edge changed the capacity)?
November 9th, 2008 at 2:54 am
the current flow is a max flow, and yes you have to update the *max* flow.
November 9th, 2008 at 4:49 pm
For problem 4, can we assume the availability of augmenting paths in the original network that resulted in a flow of value k ?
November 9th, 2008 at 4:52 pm
This goes back to my comment to Dafang: imagine that the original structure is known to you, and so you *do* have augmenting paths. the problem now is that something is wrong with the picture of the network, and you have to troubleshoot
November 9th, 2008 at 7:44 pm
In question 5, when we say “augment a graph M with an augmenting path P’, does it mean that the updated graph is M’ = M \delta P, and |M’| = |M|+1? This is inferred from the information given by the mid-exam.
November 9th, 2008 at 8:09 pm
Well I mean, run one step of FF using this path P. So yes, it means what you say, but that can be inferred independently of the midterm (I don’t want you all scrambling off to look at it :))
November 10th, 2008 at 3:44 pm
On problem 1a, what is considered an efficient algorithm?
November 10th, 2008 at 3:48 pm
When I say efficient, it’s shorthand for “do the best you can and the closer you get to what I know to be the correct answer, the more points you get”
November 10th, 2008 at 4:45 pm
On question 4.2a, do we need to find the actual set of vertices, or can we just find the number of items in the set?
November 10th, 2008 at 4:47 pm
both