Polynomially Equivalent Pairs of Minimization-Maximization Problems in Weighted Graphs

Question

I am studying computational complexity using Papadimitrious's book: "Computational Complexity". I am trying to solve Problem 9.5.14, about polynomially equivalent minimization-maximization problems in weighted graphs:

Consider the following pairs of minimization-maximization problems in weighted graphs:

(a) - MINIMUM SPANNING TREE and MAXIMUM SPANNING TREE (we seek the heaviest connecting tree).

(b) - SHORTEST PATH (recall Problem 1.4.15) and LONGEST PATH (we seek the longest path with no repeating nodes; this is sometimes called the TAXICAB RIPOFF problem).

(c) - MIN CUT between $s$ and $t$, and MAX CUT between $s$ and $t$.

(d) - MAX WEIGHT COMPLETE MATCHING (in a bipartite graph with edge weights), and MIN WEIGHT COMPLETE MATCHING.

(e) - TSP, and the version in which the longest tour must be found.

Which of these pairs are polynomially equivalent and which are not? Why?

Let's denote an edge $e \in E$ that connects vertex $u$ and $v$ and has weight $w_e$ as $e = (u, v, w_e)$. Let $M = max(|w_e|) + 1$. I was able to solve some of them by using the following reduction: given a graph $G = (V, E)$ construct the graph $G' = (V, E')$ where you construct the set $E'$ as follows: for each edge $e = (u, v, w_e) \in E$ add the edge $e' = (u, v, M - w_e)$ to $E'$. For some of the mentioned problems, the minimization version in graph $G$ is equivalent to the maximization version in graph $G'$.

I was able to solve itens (a), (d) and (e) using this trick. I am not sure if this trick applies to (c), and I think it does not work for (b).

Can anyone tell me if my attempt at itens (a), (d) and (e) are correct? Also, how do I solve itens (b) and (c)? Thanks in advance.

Answer 1

For item (b), the reduction does not work. To understand why, imagine a graph with all edges having the same weight. Then, the reduction has no effect: $G = G'$. Finding the shortest path from $u$ to $v$ consists in finding the path with fewer intermediate nodes, while finding the longest path, consists in finding the path with the highest number of intermediate nodes. The problems are not polynomially equivalent because the shortest path is in $P$ while longest path is in $NP$ (see here).

For item (c), the optimization problem for MAX CUT is NP-hard while for MIN CUT is polynomial. However, when you consider the version of these problems that allows both positive and negative weights they can be trivially converted to each other by flipping the sign in all weights.