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 aresimple 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.
Finding simple cycle of minimal weight in directed bipartite complete graph with negative cycles
algorithms;complexity theory;graphs;optimization