Finding a minimal subgraph containing all negative loops

Question

I am stuck in the following problem: given a weighted digraph G, I would like to construct a minimal subgraph G containing all negative (simple) cycles G.

I know how to find a negative cycle using Bellman-Ford, and I know that the number of simple cycles in a directed graph is exponential.

One naive way to approach the problem would be to simply iterate over all the simple loops and select the negative ones, but I feel like there might be a polynomial time algorithm. Most of the articles I have found through Google have dealt with the search for the negative cycle (and not all).

I hope to find some experts here in stackoverflow who can give some hints of a solution with polynomial time or hints of proving that it cannot be resolved in polynomial time.

Thank you very much in advance!

Cheers, Robert

Answer 1

For anyone interested or stuck in a similar problem: it's NP-complete. Thanks to the fact that I pointed to the thread in cstheory.

To understand why it is NP-complete, first of all, we note that the problem can be formulated as follows: taking into account a weighted directed graph G with N verifications and an edge E on G, find out if E lies on a (simple) negative cycle. If so, E should be in subgraph H. If it is not, it should not be in H.

Now let the edge E be equal to E = (u, v) with weight w. We would like to know if there exists a path from v to u with a total weight W such that W + w <0. If we could do it in polynomial time, we could also solve the Hamiltonian cycle problem in polynomial time:

Give edge E a weight of N - 1.00001. Assign all other edges in the graph a weight of -1. Now the graph of only the negative cycle on which E lies is a cycle containing all the vertices (this cycle has a weight of -0.00001) and, therefore, is a Hamiltonian cycle.

Thanks so much for thinking!