Is there an efficient 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 vertices with $G$. You can look to this paper for the definition. In this paper the authors present an approximation for the minimum strongly connected subgraph problem, which is different from the problem stated in this question.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy