3
$\begingroup$

In a Multiterminal Cut problem input is a graph G=(V,E) and a set of k terminals T which is a subset of vertex set V. There is a weight w(e) associated with each edge in the graph. The question is to find the minimum weight edge set whose removal will disconnect every terminal to every other terminal in T. The following things are known about the problem:

  1. k = O(1), Degree of any vertex unbounded, edge weights = O(1) APX hard
  2. k = O(1), Degree of any vertex = O(1), edge weights unbounded APX hard
  3. k unbounded, Degree of any vertex = O(1), edge weights = O(1) NP hard
  4. k = O(1), Degree of any vertex = O(1), edge weights equal Poly time.

Is there a result which says that the problem with " k unbounded, Degree of any vertex = O(1), edge weights = O(1)" is also APX-hard? Any ideas on proving this will be useful.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.