Suppose that I have a MAX CUT problem on a weighted undirected Graph $G$, but there is an oracle that tells me what the value of the MAX CUT is, but not which edges produce it. Does this make the problem any easier?

Added later: to clarify what I want: the oracle only tells you the value of max cut for the original graph, not for any of the modified graphs as in Austin's answer.

  • 2
    $\begingroup$ What are restrictions on the oracle? Do you only get one call? If not, help me understand why the oracle can compute max cut on an $n$-vertex graph, but not an $(n-1)$-vertex graph. $\endgroup$ – Austin Buchanan Nov 14 '13 at 4:38
  • $\begingroup$ It would allow you to enumerate candidates for the cut by solving a subset sum problem (finding all subsets of edges whose weight sum to the desired value). In some cases that might be faster, though I don't have any reason to expect it would be in general. In any case, the problem seems like it lacks any obvious motivation. Where did you come across this problem? What's the context, and why does it interest you? $\endgroup$ – D.W. Nov 14 '13 at 6:01
  • 1
    $\begingroup$ You are essentially asking if there is a very efficient reduction from the search problem of finding the edges to the self-reduction of finding the max-cut with only one call to the oracle and only on the input. I doubt it can be done because of the following intuition: I think it is possible to make an input of size $n$ with "many" max-cuts with a fixed value (so you don't even need the oracle) but such that finding any of them is "hard". $\endgroup$ – Kaveh Nov 14 '13 at 23:08

Let's consider unweighted graphs, which is still a hard problem. Say you have an algorithm that solves your problem in time $T(n)$. Then I could solve the MAX CUT problem without such an oracle in time $O(m\cdot T(n))$, where $m$ is the number of edges in the graph.

Run $m+1$ versions of your algorithm in parallel, each of which gets a different value for the MAX CUT from the "oracle". Note that $m$ out of these $m+1$ runs will get an incorrect value from their "oracle", but one of them will get the correct one since the true MAX CUT value must be between $0$ and $m$.

After you performed $T(n)$ steps in each of these runs, the run that found the largest cut will have found the MAX CUT.

So no, in general it does not help significantly to have such an oracle.


Yes. You could find the actual cut using $n$ calls to the oracle.

Let the vertices be labeled $1, \dots, n$. Add a dummy vertex $0$ with outgoing edge weights equal to zero. For each vertex $j=2,\dots, n$ tentatively merge $j$ with vertex $1$. If the max cut objective remains the same, leave $j$ and 1 merged. Otherwise, merge $j$ with $0$ instead.

  • $\begingroup$ Thanks. However in my question the oracle is only available for the original problem, not any of the subproblems. Perhaps I didn't make that clear enough. I was thinking that in a sort of branch and bound where each branch either includes an edge or excludes it, one always has a tight bound, which without the original oracle wouldn't be available. $\endgroup$ – Victor Miller Nov 14 '13 at 3:47

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.