Finding strongly connected subgraph that contains no negative cycles

Question

Is there an algorithm that solves the following decision problem:

Given a strongly connected weighted directed graph G, defined by its transition matrix, is there a strongly connected spanning subgraph of G that has no negative cycles?

A strongly connected spanning subgraph of G is a strongly connected subgraph of G that shares the same vertexes with G. You can look to this paper for the definition of strongly connected spanning subgraph. In this paper they present an approximation for the minimum strongly connected subgraph problem.

A naive approach to this problem is to find a negative cycle of the graph using the Ford-Bellman or Floyd-Warshall algorithm, deleting an edge from this cycle, and repeating while the graph is still strongly connected. But this naive approach has poor time complexity because we will potentially run the Ford-bellman algorithm and check for strong connectivity many times -- moreover I am unable to prove if this algorithm is correct in all instances.

I'm hoping to find experts here who can tell me if this decision problem can be solved in a polynomial time and what algorithm does so. Many thanks in advance.

Did you mean maximal subgraph? Minimal subgraph can be two nodes and two edges ;) — Yonlif
[Not an expert] just brainstorming, perhaps you could detect cycles via Tortoise and Hare modified to store total weight from starting point, if you arrive at an already already assigned node then you have a cycle and the difference in current total weight and assigned would indicate if negative. Dynamic programming could limit the number of starting points you need to use. The assignments would need to be cleared for each new starting point run. — karmakaze
You didn't address @Yonlif 's comment. G:{A->B, B->A} is a strongly connected graph. Will such subgraph be acceptable in this problem? — jrook
@othmanmarfoq It is usually a good idea to add all definitions and criteria to the question body. At least add these basic definitions (and necessary links) to the question body so others who have the same problem in the future can follow up. — jrook

btilly btilly · Accepted Answer · 2019-12-30T21:50:30

Here is a naive solution that has a reasonable chance of finding a strongly connecting spanning subgraph with no negative cycles in polynomial time. But is emphatically not guaranteed to find one.

Turn all weights to their negatives. Now use Ford-Bellman or Floyd-Warshall to find a negative cycle. This is actually a positive cycle in the original graph.

Now we pick one vertex in the cycle, and contract the other vertices to it. Edges that connect to/from removed vertices are replaced by ones representing traveling along that edge and around the cycle to the one we keep. If you wind up with multiple edges between two vertices, only keep the best one.

Repeat the exercise on the new, smaller, graph.

This algorithm runs in guaranteed polynomial time (each iteration runs in polynomial time and removes at least one vertex). If it manages to reduce your graph to a point, then you just walk the process backwards and find that you have in fact found a strongly connected spanning graph with no negative cycles.

However if it fails to do so, there is no guarantee that there isn't one. You just didn't find it.

(I suspect that a guaranteed algorithm will be NP-complete.)

Finding strongly connected subgraph that contains no negative cycles

2 Answers