5

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.

hola
  • 592
  • 5
  • 19
  • I'm not familiar with all the terms (graph theory study was a long time ago for me). This sounds like a proof sort of question rather than an algorithm type, where is says 'Is there...' rather than 'Find...'. Or are you working on algorithmic provers? Also the title says 'minimal' where the problem mentions 'strongly connected' instead. – karmakaze Dec 30 '19 at 18:01
  • 2
    Did you mean maximal subgraph? Minimal subgraph can be two nodes and two edges ;) – Yonlif Dec 30 '19 at 18:04
  • @Yonlif I am sorry, a mistake in the title, I ment strongly connected. I will edit it. – hola Dec 30 '19 at 19:17
  • 1
    @karmakaze The question is indeed 'Is there...', I edit it. – hola Dec 30 '19 at 19:19
  • The name `Floyd` sounds familiar so I looked up (unrelated) [Floyd's Tortoise and Hare](https://en.wikipedia.org/wiki/Cycle_detection#Floyd%27s_Tortoise_and_Hare) which I've used but may have been misattributed by Knuth. – karmakaze Dec 30 '19 at 19:55
  • 1
    [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 Dec 30 '19 at 20:00
  • 1
    @karmakaze The procedure you are proposing here, answers the question: "Is there any negative cycle in the graph?" As I mentionned this is an "easy" question to answer, we have good algorithms to solve as the Ford-Bellman or Tortoise-Hard algorithm. But the main question is about the existance of a subgraph that doesn't contain any negative cycles. – hola Dec 30 '19 at 20:19
  • @karmakaze This is a lot more challegning question, because we not only want to know if the graph has a negative cycle, but if one of its strongly connected subgraphs has no negative cycles. It is to note that the problem of finding a minimal strongly connected subgraph is NP-hard [link](https://www.researchgate.net/publication/220779385_Approximating_the_minimum_strongly_connected_subgraph_via_a_matching_lower_bound) however we have good approximate methods for the problem of minimum strongly connected subgraph. – hola Dec 30 '19 at 20:20
  • 2
    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 Dec 30 '19 at 20:26
  • 1
    @jrook When I said minimal I ment in the sense of edges not vertexes, In fact we are looking for a mninmal spanning strongly connected subgraph that has no negative cycles. If you want a more definition of a minimal spanning graph, it is provided in [link](https://www.researchgate.net/publication/220779385_Approximating_the_minimum_strongly_connected_subgraph_via_a_matching_lower_bound) – hola Dec 30 '19 at 20:41
  • 2
    @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 Dec 30 '19 at 20:50
  • 1
    @jrook That's a good advice, thanks I will do it. It is the first I ask a question here, so I don't really kno the rules. – hola Dec 30 '19 at 20:51
  • a "spanning" subgraph is one that includes all of the vertices of G right? – jwezorek Dec 30 '19 at 21:08
  • @jwezorek Yes exactly, I have edited the question and added this definition – hola Dec 30 '19 at 21:09

2 Answers2

0

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.)

btilly
  • 43,296
  • 3
  • 59
  • 88
  • Thanks for the answer, the only problem is that the question is about finding a subgraph that shares the same verteces with G, i.e the set of verteces should be unchanged. If I have well understand your method it consists in reducing the number of verteces at each iteration, isn't it ? – hola Dec 30 '19 at 22:34
0

This problem is NP hard in general, this can be proven by reducing Hamiltonian cycle into it.

hola
  • 592
  • 5
  • 19