I know that the problem of checking whether given edge of a weighted digraph belongs to a negative cycle is NP-complete (Finding the minimal subgraph that contains all negative cycles) and Bellman-Ford allows to check a vertex for the same thing in O(|V|*|E|) time. But what if I want to find all vertices belonging to negative cycles? I wonder if it could be done faster than Floyd-Warshall's O(|V|^3).

I don't think Floyd-Warshall does the job of finding these vertices. Using a similar approach as taken in the post you're referring to, it can be shown that finding the set of all vertices that lie on a negative cycle is NP-complete as well.

The related post shows that one may use the algorithm to find the set of all edges that lie on a negative cycle to solve the hamiltonian cycle problem, which means that the former problem is NP-complete. If we can reduce the problem of finding all edges that lie on a negative cycle to the problem of finding the set of all vertices that lie on a negative cycle, we've shown NP-completeness of the latter problem.

For each edge (u,w) in your weighted digraph, introduce a new auxiliary vertex v, and split (u, w) in two edges (u, v) and (v, w). The weight of (u, w) can be assigned to either (u, v) or (v, w). Now apply the magic polynomial-time algorithm to find all the vertices that lie on a negative cycle, and take the subset that consists of the auxiliary vertices. Since each auxiliary vertex is associated with an edge, we've solved the problem of finding the minimal subgraph that contains all negative cycles, and we can thus also solve the hamiltonian cycle problem in polynomial time, which implies P = NP. Assuming P != NP, finding all vertices that lie on a negative cycle is NP-complete.

Similar Questions

We got a special multivalue attribute. Let's call it ourOwnManagedBy which can contain users or groups (their DN) that manages the current group. How can I retrieve a list of all groups that a specifi

I have code written for calculating the no of cycles in a directed graph using DFS. The method to check if a cycle exists or not works fine. I now iterate through all the vertices (which I have in a H

From SUSv4: If pid is negative, but not -1, sig shall be sent to all processes (excluding an unspecified set of system processes) whose process group ID is equal to the absolute value of pid, and for

I am having a hard time understanding clock cycles. Here is the problem, I am given a program that has two instructions X and Y and I know that X is run 20% of the time and requires 8 clock cycles and

C# arrays, why not have an array with a negative number as index? This situation is sometimes very useful; especially for a fast algorithm in some special type of sorting. Two questions: 1) Why not? 2

One piece of the program I am writing in Prolog has to do with finding all possible path options from the starting location to the ending location. Here is what I have so far: findAllRoutes(Start, End

When I use immediate mode, it draws correctly but when i pass the same vertices to the GPU, or even point them, it doesn't work. there is a position buffer holding vertices : std::vector<glm::vec3&

I am using QuickGraph to create a directed acyclic graph. I need to find all vertices whose indegree is zero. I don't see this support on a graph's Vertices collection, or a way to filter using LINQ.

How could one go about finding where in memory a running java program was storing the bytecode it was running off of? I appreciate this may or may not be excruciatingly difficult.

Given an array consisting of equal number of positive and negative numbers (0 being considered as positive). Rearrange the elements such that positive and negative numbers are placed alternatively, in

I find cleaner and easier to work with keeping those elements in separate buffers, but I wanted to know if it performs better having them all in one big buffer.

I am creating a game and I need to generate some game pieces. Each piece is an array consisting of 4 numbers(each represents a property of the piece) ranging from 0-2. I need to generate all combinati

I'd like to filter edges by comparing one property of each edge's vertices. This is the Gremlin code I hoped would return all edges where the vertices have the same GROUP_NAME as one another: g.E.filt

We are given a directed graph G (possibly with cycles) with positive edge weights, and the minimum distance D[v] to every vertex v from a source s is also given (D is an array this way). The problem i

I need a regular expression (dubbed SOME_EXPRESSION below) that allows finding all namespaces for resources used as subject in a SPARQL 1.1 endpoint. The query should look like the following. How can

I'm trying to figure out this problem. I have a matrix with integer values. The goal is to get it so that every row sum and every column sum is non-negative. The only things I can do are change the si

Please give me pseudocode for finding cycles using BFS. I know other questions of this type exist but NONE give the code.

I need to find a way to enumerate all my iPhone application's active threads. This is strictly for debug purposes. Private APIs, if any, are welcome as well. I know I can see all the current threads i

I am using SUM() function. But SUM() sums the negative value in the column. In a column if the value is positive then it should be added and for negative values should be substracted and not added as

I create a VBO in a function and I only want to return the VBO id. I use glDrawArrays in another function and I want it to draw all the vertices in the VBO without needing to also pass the number of v

In a DAG G, with non negative weighted edges, how do you find the maximum-weight path between two vertices in G? Thank you guys!

How can I produce all of the combinations of the values in N number of JavaScript arrays of variable lengths? Let's say I have N number of JavaScript arrays, e.g. var first = ['a', 'b', 'c', 'd']; var

I am using the following code to get the R,G,B values for a grayscale image(they all will be the same) But the output gives me negative values. Why is this so? I am totally confused. for (int i=0;i<

In Python, how would one find all integer points common to two circles? For example, imagine a Venn diagram-like intersection of two (equally sized) circles, with center-points (x1,y1) and (x2,y2) and

Given a triangle in 3D and a point on one of its edges, I want to find out which of the vertices of that edge is to the left of that point, and which is to the right. Please see the image below: In t

I am following the algorithm in this PDF in order to find all candidate keys for my relation from the given functional dependencies. I have found that all my attributes are middle ground attributes an

Let G = (V;E) be a directed graph whose edges all have non-negative weights. Let s,t be 2 vertices in V, and let e be an edge in E. Describe an algorithm that decides whether all shortest paths from s

I am using opencv with opencvsharp. When doing a matchtemplate and afterwards minmaxloc I only get the first match. How do I get all matches? Cv.MatchTemplate(tempImg, templateSymbol.Img, resImg, Mat

Is there a good and fast way in C/C++ to test if multiple variables contains either all positive or all negative values? Say there a 5 variables to test: Variant 1 int test(int a[5]) { if (a[0] < 0

I got 2 no.of Circle, clicking big circle i am finding small circle using the class name and trying to animate the small circle, but not working at all. But fadeId, fadeOut properites are working. My

What is the best way, or are there any ways implemented in are to count both 3 and 4 cycles in networks. 3 cycles equal connected groups of three nodes(triangles) to be calculated from one mode networ

Let's say I have the following table first last value tony jones 1 james guy 5 sara miller 6 tony jones 2 sara miller 3 joe cool 4 david marting 7 Is there a command to quickly query all duplicate ro

I'm a complete newbie in 3D and I'll like to ask if there are any good tutorials on 3D Vertices out there. I've tried googling for it but came up empty. Thanks!

Now trying to figure out how to find all the maximal subsequences(both positive and negative) in sequence. Here I got some troubles, because there is no suitable solution found. I've this code, but th

I have an NSMutable array of NSNumbers, which were converted from NSInteger values. In the case that I have a mix of negative and positive numbers, I end up with the result that the smallest positive

Enumerating all simple paths between two vertices in an arbitrary graph takes exponential time in general, because there may be an exponential number of simple paths between the vertices. But what abo

is there any algorithm or is there any name for a transformation of a graph where one can transform edges into vertices and vertices into edges? Just so we could get a new graph out of it or anything

I'm trying to use the Amazon AWS Command Line Tools to find all instances that do not have a specified tag. Finding all instances WITH a tag is simple enough, e.g. ec2-describe-instances --filter tag

I've implemented delta time in my game loop so that any fluctuations in frame rate don't matter any more, however won't the game still run faster on faster machines and slower on slow ones? I was unde

I have requirement to find all the text nodes and create new node sequence(see in input/output XML), and if any inline nodes (preceding-sibling or following-sibling of text node), then rename those ta

I have some properties defined by the user, and then I want use them to automatically generate a regular polygon. The properties are centre x, centre y, radius and number of vertices. I would like to

I am having a simple program, it draws a circle :/ This works fine... for (k = 1; k < n+1+1; k++){ vertices[k].color = GU_COLOR( 0.0f, 0.0f, 1.0f, 0.0f ); vertices[k].x = cos_d( 360 - ((k-1) * dste

I am looking for an algorithm to find all the nodes between two certain nodes of a directed graph. For example, the nodes between nodes a and j in the graph shown below are: b c d e f g h i P.S.

Is there a built-in function in java that would convert any negative number to a 0? what i'm wanting to do is subtract number from a variable, and ensure that it doesn't go below 0. is this possible w

Given G, a directed graph, is there a path (not necessarily a simple path) that goes through all the vertices in G? I first need to examine what happens in an acyclic graph and in a strongly-connected

Given a package, how can I automatically find all its sub-packages?

I have a midpoint (x,y) and i need to find (in elegant and python style) a vertices of square with rotation for a given angle (t) or random adding to my function a parameter t (angle), when t is equal

I'm trying to get all the texture coordinates and all the vertices of a glGenList in two separate lists with c#. I need a function that can do it. Is this possible?

I am reading several books about OpenGL and in two of them they always define the vertices counter clockwise. From what I read this is very crucial because it determines where the front and back is. B

Given a weighted undirected graph with n vertices, I face the problem of finding a path of minimum weight that connects each of the vertices in a line. At first, I thought this is the problem of findi