3
$\begingroup$

Given a weighted complete bipartite directed graph K_{m,n}, is it possible to find a simple cycle (every node is visited at most a single time) with minimal weight in polynomial time (in m*n) when there exist simple cycles with negative weight?

For general graphs this problem is NP-complete (Finding the lowest-weight negative cycle in a weighted digraph). Using Bellman-Ford it is possible to find a cycle with negative weight if such a cycle exists, but this algorithm gives no guarantee that it is the most negative cycle.

In total there are enter image description here

simple cycles in this graph, so checking all of them would already give a subexponential algorithm. But can this be reduced to a polynomial time algorithm?

Some assumptions I can make:

  • The absolute value of the weights are bounded by a constant C.
  • There exists a negative simple cycle and all negative simple cycles visit at least 4 nodes.

Thanks.

$\endgroup$
1
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$
    – Raphael
    May 24, 2016 at 11:01

1 Answer 1

1
$\begingroup$

No.

That is, there is no polynomial time algorithm in $m\times n$ that can find a simple cycle with minimal weight in any given weighted complete bipartite directed graph K_$\{m, n\}$ in the sense that it is a NP-complete problem.

To prove it, let us reduce the undirected Hamiltonian cycle problem, one of Karp's 21 NP-complete problems, to the current problem by a polynomial-time reduction.

Let $G$ be an undirected graph with vertices $V$ and edges $E$. For each vertex $u$ in $G$, we create two new vertices, $u_{in}$ and $u_{out}$. Let $V_{in}=\{u_{in}|u\in V\}$. Let $V_{out}=\{u_{out}|u\in V\}$. Let $K$ be the complete bipartite digraph connecting the vertex sets $V_{in}$ and $V_{out}$. For every vertex $u\in G$, both edges $(u_{in},u_{out})$ and $(u_{out}, u_{in})$ in $K$ weigh 0. If edge $(u, v)$ is in $G$, then the both edge $(u_{out},v_{in})$ and edge $(v_{out},u_{in})$ in $K$ weigh $-1$. Any other edge in $K$ weigh $|V|$. $K$ with its edge-weights thus defined is a weighted complete bipartite directed graph with $|V|$ vertices in each of its two vertex sets (that is, $m=n=|V|$ for $K$).

Each simple cycle in $G$ corresponds to a simple cycle in $K$ with the same weight in the natural way as illustrated by the following example. A cycle $a, b, c, a$ in $G$ corresponds to the cycle $a_{in}, a_{out}, b_{in}, b_{out}, c_{in}, c_{out}, a_{in}$ in $K$. In particular, a Hamiltonian Cycle in $G$ corresponds to a simple cycle in $K$ of weight $-|V|$. Conversely, it is easy to see that a simple cycle of weight $-|V|$ in $K$ corresponds to a Hamiltonian Cycle in $G$ under the same correspondence. Note that a simple cycle of weight $-|V|$ in $K$ must be simple cycle of minimal weight in $K$.

Assume we can find a simple cycle $C$ of the minimal weight in $K$ by some algorithm. We can then check the weight of $C$. If the weight of $C$ is $-|V|$, the simple cycle in $G$ that corresponds to $C$ is a Hamiltonian Cycle. Otherwise, there is no Hamiltonian Cycle in $G$. So we have reduced the undirected Hamiltonian cycle problem to the current problem. We can see easily that this reduction is a polynomial-time reduction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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