## Negative cycle detection using bellamn ford and its correctness

I recently started studying algorithms on my own using corman and mit algo videos in youtube. I am going thru bellman ford.

I have 2 doubts in correctness of algorithm

1) why are we relaxing (num of vertices – 1) times all the edges. Why not some finite number of times till earlier values and new values remain same.

2) Second for loop(lines 5,6,7 in algo image) is for detecting negative edge cycle. THen i have gone through this correctness. I have seen a theorem that if there is a negative edge cycle reachable from source s then we can find an edge uv such that d(v)>d(u)+w(u,v) [I understood the proof by contradiction(if summing all vertices of negative edge cycle results in sum of all weights along negative cycle positive which means contradiction as it must be negative – page 2 of https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture14.pdf]

But i am not able to visualise such an edge if i have some negative edge cycle from source vertes s. Please help me how such edge exists?

Suppose i have the following resource allocation graph with a deadlock cycle, i see why it is a deadlock cycle, what i don’t get is how to recover from this cycle

i’m thinking about aborting a process, any process here will lead to non-deadlock situation, but doesn’t that cause the other process to not execute and hence the program won’t execute as we’re expecting it to be, i think this is a correct answer, but is there another way to do such that all processes will eventually run ?

## The average weight of a cycle in graph

I have a weighed undirected graph. How is possible find the minimum average cycle weight. The average weight of a cycle is the weight of this cycle divided by the number of edges in it. And I must return the answer up to $$\varepsilon$$.

## Shortest cycle for each vertex

I have an unweighted undirected graph.How is it possible in this graph for each vertex to find the length of the shortest cycle containing it?

## How to find the shortest even length cycle in a bipartite graph?

If you have n vertices and m edges, how would you find the shortest cycle of a bipartite graph in O(n^2) time? To do it in O(nm) time, it is simply a BFS on every single vertex. I do not understand how you can do it just by going over every single vertex. I know you would have to stop at non-tree edges to do so, but how would you use this type of technique to guarantee this runtime and find the shortest cycle? Could anyone give me some sort of advice or help?

## Detecting a cycle in an undirected graph and printing the vertices if there is a cycle, printing no cycle otherwise

Problem: Find an O(E + V) time algorithm that outputs the vertices of a cycle of G, if it exists. If G has no cycles, the algorithm outputs no cycle. So if there is a cycle 1, … 3, 1, it would print 1, …, 3, 1.

So I was thinking of doing a BFS, and if the currently examined vertex’s neighbor v has been visited prior, then there is a cycle. However, I am not sure how I might go about tracking the vertices in order to print. I believe I would have to view the BFS-Tree, but unsure.

## Floyd’s Algorithm with a negative cycle

I know that I cannot use Floyd’s algorithm if I have a graph with at least one negative cycle, because path-lengths between vertices can be arbitrarily small.

I am wondering, how the distance matrices at each iteration of $$k$$, where $$k=0, \dots n$$ will look like. I now that there will be negative numbers on the main diagonal, but I do not know where they will be. Could somebody explain it to me, please?

I have example with 4 vertices and I know that matrix for $$k=0$$ is the same as in the case that there are no negative cycles in a graph.

My example (but you can use another graph):

Matrix for $$k=0$$ is:

$$\begin{bmatrix} 0 & -4 & \infty & 3 \ 1 & 0 & \infty & \infty \ \infty & 2 & 0 & \infty \ \infty & \infty & 5 & 0 \end{bmatrix}$$

## Detected if an undirected graph G has a cycle

Trying to understand complexity well, I found myself with the following problem.

Consider the following algorithm to detect if an undirected graph $$G = (V, E)$$ has a cycle.

Imagine that $$V = \{1 …|V|\}$$ (in other words that the vertices are numbered from $$1$$ to $$|V|$$ ). An explorer plants a flag on point $$1$$ and then moves on the graph according to the following principle.

• For each vertex $$u \in V$$ the different edges $$(u,v)$$ around the point $$u$$ can be ordered according to the size of $$v$$. So we can talk about the ith edge around $$u$$. . Note that if $$(u,v)$$ is the ith edge around $$u$$ it is possible that $$(v,u)$$ is not the ith edge around from $$v$$.
• If the explorer reaches the point $$u$$ of degree $$k$$ using the ith edge around $$u$$ then it starts from $$u$$ using the $$(i + 1)$$ th edge around from $$u$$. If $$i = k$$ then the explorer starts from the first edge around $$u$$.

As a first attempt, the explorer leaves point $$1$$ using the first edge around $$1$$. If it returns to point $$1$$ by a different edge then he concludes that $$G$$ contains a cycle.

If on the other hand it returns to point $$1$$ to across the same edge, then it begins its exploration again, starting by the second edge of point $$1$$, then the third edge and so on.

If he has exhausted all edges around $$1$$ and has always returned to $$1$$ by the same edge, so he plants his flag on point $$2$$ and so on.

My questions are :

1. how can we show that $$G$$ contains a cycle if and only if there is a point $$u$$ and an edge $$(u,v)$$ around $$u$$ such that the explorer leaving $$u$$ by the edge $$(u,v)$$ does not return to $$u$$ by $$(u,v)$$.
2. What is the is the space complexity of the algorithm described here?

## The existence of a cycle in a directed graph is a NL-complete?

Show that the problem of the existence of a cycle in a directed graph is a $$NL-complete$$ problem.

I have already successfully demonstrated that this problem $$\in NL$$. But I’m stuck on how to take it apart that it’s $$NL-hard$$.

To show that the problem is $$NL-hard$$, we can start from problem $$s; t-connectivity$$ and as an intermediate step, create a acyclic graph $$G^a$$ which is $$s’; t’- connected$$ if and only if the original graph $$G$$ is $$s; t- connected$$. Using the length of the paths of a vertex $$x$$ at a vertex $$y$$.

L ← Empty list that will contain the sorted nodes while exists nodes without a permanent mark do     select an unmarked node n     visit(n)  function visit(node n)     if n has a permanent mark then         return     if n has a temporary mark then         stop   (not a DAG)      mark n with a temporary mark      for each node m with an edge from n to m do         visit(m)      remove temporary mark from n     mark n with a permanent mark     add n to head of L