1
$\begingroup$

A graph with n vertices, no matter directed or not, may have maximally 2^n-n-1 negative cycles

(Think about combination of 2 to n elements and you'll figure out why 2^n-n-1. A graph that has no graph loops or multiple edges is my only concern)

and I want to find ALL of them if any, not just one of them. There are only answers to the latter question throughout the whole internet. To find a cycle means we get a list of vertices which form this cycle.

I also want to find the one negative cycle which is the smallest in one lap of traverse.

One solution, which is slow and not elegant, is to run Floyd-Warshall algorithm on the graph, and find those vertices, e.g. i, so that d[i][i]<0 (According to some researches collected in Wikipedia, this means vertex i is part of a negative cycle) and then check all 2^n-n-1 (if there are n of those i's) cycles to see if they are negative.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ A graph can have more than $2^n$ negative cycles. In a clique of $n$ vertices the cycles of length $n$ are already at least $(n-1)!/2$ (fix a vertex, every permutation of the remaining $n-1$ vertices induces a cycle and each of these cycles is counted twice). $\endgroup$
    – Steven
    Commented Jan 9, 2021 at 16:19
  • $\begingroup$ @Steven I forgot to note that a graph that has no graph loops or multiple edges is my only concern (If there are edges a->b and b->a in a directed graph, they are not multiple edges, but two a->b's are). In this sense, permutation should be replaced with combination. For instance, a->b->c->a and b->c->a->b should be considered the same cycle. $\endgroup$
    – mingzi xingshi
    Commented Jan 11, 2021 at 3:04
  • $\begingroup$ @PålGD I can not provide more information because the question itself is general, or strong. The graph can be small or big, dense or sparse. You can assume it is sparse to look for a polynomial time complexity algorithm if possible, then we actually get a good but weaker solution, and I wish our solution is strong. I already showed a possibly non-polynomial time complextity solution, and I am looking for any better one. $\endgroup$
    – mingzi xingshi
    Commented Jan 11, 2021 at 16:00
  • $\begingroup$ Ooops, I just realized that we just cannot make it in polynomial time complexity for that negative cycles themselves can be exponentially many. Maybe we can't make it any better than the solution I provided. $\endgroup$
    – mingzi xingshi
    Commented Jan 11, 2021 at 16:03
  • $\begingroup$ @Steven's construction does not use loops or multiple edges, so it holds even in graphs without them. $\endgroup$
    – j_random_hacker
    Commented Jan 12, 2021 at 13:54

1 Answer 1

Reset to default
3
$\begingroup$

First of all, there can be exponentially many negative cycles, as @Steven already mentioned. Take $K_n$ with only negative edges. Enumerating all of them will be bound to take exponentially long time.

You also say that you want to find the most negative cycle in the graph (which should be simple if you enumerate them all), however, in case you want a special algorithm for this problem, note that this problem is NP-complete; the reduction from Hamiltonian is straight forward.

Since you ask for any algorithm, just run, for every subset of vertices, a DP algorithm to find the Minimum Hamiltonian Cycle for that induced subgraph. (Since you don't want to revisit an edge, you can probably find a way to add $\min_{e \in E(G)} w(e)$ to every edge, thereby avoiding all the negativity.)

(P.s., OP stated in a comment that cycles on the same vertex set are considered equivalent.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.