1
$\begingroup$

I'm asking because it seems that P problems refer to decision problems rather than actually propose a solution.

$\endgroup$
3
$\begingroup$

If you have available a TSP decision oracle -- that is, a function that answers questions of the form "Does directed graph $G$ have a TSP tour of length at most $k$?" in constant time -- then the following algorithm will allow you to construct an actual TSP tour using $O(|E|)$ calls to the oracle, and $O(|E|^2)$ time overall:

  1. Run a binary search on $k$, calling the decision oracle at each step, to determine $OPT$, the minimal tour length of the original graph $G$. (If necessary, the absence of any Hamiltonian cycle at all can be first tested for by calling the oracle with a very large threshold -- e.g., equal to the sum of all edge weights.)
  2. If $G$ contains 3 or fewer edges, then stop. (These must form a triangle.)
  3. Choose an arbitrary vertex $u$ in $G$.
  4. For each out-edge $uv$ in $G$:
    • Create a new graph $G'$, which is the same as $G$ except that the edge $uv$ has been collapsed (specifically: delete vertices $u$ and $v$ and all edges they are incident on, and create a new vertex $x$ that has all of $u$'s incoming edges and all of $v$'s outgoing edges).
    • Run the decision oracle on $G'$ with the length threshold $OPT-w(uv)$.
    • If the answer is YES, then some optimal solution to $G$ contains the edge $uv$: Replace $G$ with $G'$ and $OPT$ with $OPT-w(uv)$ and go to 2.
    • If the answer is NO, then no optimal solution to $G$ contains the edge $uv$: Delete $uv$ from $G$, and continue iterating through other out-edges of $u$ in $G$.

The iterations in the loop beginning at step 4 execute at most $|E|-3$ times. How quickly the graph modification steps (edge collapsing, edge deletion) in each iteration can be performed probably depends on the graph representation used, but they can certainly be done in $O(|E|)$ time each, for $O(|E|^2)$ time overall, which is enough to show the algorithm is polynomial. (Can anyone think of faster $O(|V|)$ or even $O(|1|)$ ways to perform these modifications?)

The above runs on a directed graph $G$. If you have an undirected graph, you can first turn each undirected edge into a pair of opposite-facing directed edges having the same weight, and then run the algorithm as before.

$\endgroup$
0
$\begingroup$

Optimization version and decision version could be exchanged (binary search). That's why only decision version is studied.

$\endgroup$
  • 2
    $\begingroup$ (1) If what you want is simply the minimum or maximum function value (here, the length of a shortest TSP tour), then you can certainly solve this via binary search with $O(\log n)$ calls to a decision oracle -- but if what you want is a concrete solution (here, an actual tour), it's not at all clear that this can be done in that time for every NP-hard problem. (2) Constructing such a solution can however always be done with a polynomial number of decision oracle calls, and I think what the OP wants to know is how to accomplish that for this specific problem. $\endgroup$ – j_random_hacker Apr 24 '18 at 7:24

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.