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, wich 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.
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.