Solution Found!
In the MULTIWAY CUT problem, the input is an undirected graph G = (V, E) and a set of
Chapter 9, Problem 9.7(choose chapter or problem)
In the MULTIWAY CUT problem, the input is an undirected graph G = (V, E) and a set of terminalnodes s1, s2, . . . , sk V . The goal is to find the minimum set of edges in E whose removal leavesall terminals in different components.(a) Show that this problem can be solved exactly in polynomial time when k = 2.(b) Give an approximation algorithm with ratio at most 2 for the case k = 3.(c) Design a local search algorithm for multiway cut.
Questions & Answers
QUESTION:
In the MULTIWAY CUT problem, the input is an undirected graph G = (V, E) and a set of terminalnodes s1, s2, . . . , sk V . The goal is to find the minimum set of edges in E whose removal leavesall terminals in different components.(a) Show that this problem can be solved exactly in polynomial time when k = 2.(b) Give an approximation algorithm with ratio at most 2 for the case k = 3.(c) Design a local search algorithm for multiway cut.
ANSWER:Step 1 of 3
If k=2, the problem of multiway cut becomes the same as the min-cut problem used in the maximum flow graph. Maximum flow graph problem can be solved in polynomial time.
Hence, it is proved that multiway cut problem can be solved in polynomial time if k=2