Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.

40
votes
3answers
42k views

Longest path in an undirected tree with only one traversal

There is this standard algorithm for finding longest path in undirected trees using two depth-first searches: Start DFS from a random vertex $v$ and find the farthest vertex from it; say it is $v'$. ...
23
votes
3answers
10k views

Retrieving the shortest path of a dynamic graph

I'm studying shortest paths in directed graphs currently. There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the graph is ...
35
votes
3answers
31k views

Why does Dijkstra's algorithm fail on a negative weighted graphs? [duplicate]

I know this is probably very basic, I just can't wrap my head around it. We recently studied about Dijkstra's algorithm for finding the shortest path between two vertices on a weighted graph. My ...
9
votes
1answer
5k views

Finding the k-shortest path between two nodes

Given a weighted digraph $G=V,E$, and a weight function, $d(u,v)$, one can normally use Dijkstra's algorithm to obtain the shortest path. What I am interested in, is how to obtain the $2^{nd}$-...
15
votes
1answer
13k views

Find the Simple Cycles in a Directed Graph

This problem, for me, looks very interesting. It was about to find a simple cycle (i.e. cycle where are not repeat nodes) in a directed graph. My solution is going like this, i.e, this graph is a ...
6
votes
1answer
3k views

Find a 3-colouring using the 3-colourability decision problem

I was learning about NP problems. I read that for many problems, like Clique, we can easily convert its decision problem to derive a solution of search problem. (For Clique problem, you only need to ...
25
votes
4answers
4k views

Enumerate all non-isomorphic graphs of a certain size

I'd like to enumerate all undirected graphs of size $n$, but I only need one instance of each isomorphism class. In other words, I want to enumerate all non-isomorphic (undirected) graphs on $n$ ...
20
votes
3answers
13k views

When is the minimum spanning tree for a graph not unique

Given a weighted, undirected graph G: Which conditions must hold true so that there are multiple minimum spanning trees for G? I know that the MST is unique when all of the weights are distinct, but ...
2
votes
1answer
1k views

Algorithm for solving incremental max flow problem

I am working on a project where I need to be able to compute the maximum flow between two nodes in a graph after one of the edge weights has been incremented or decremented by 1. The graph is directed ...
25
votes
7answers
38k views

Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u ...
4
votes
2answers
11k views

Is there an algorithm to find all the shortest paths between two nodes?

Given a directed graph, Dijkstra or Bellman-Ford can tell you the shortest path between two nodes. What if there are two (or n) paths that are shortest, is there an algorithm that will tell you all ...
15
votes
1answer
16k views

Find the longest path from root to leaf in a tree

I have a tree (in the graph theory sense), such as the following example: This is a directed tree with one starting node (the root) and many ending nodes (the leaves). Each of the edge has a length ...
3
votes
1answer
321 views

Expected distance between tree nodes

I have been given a tree with n nodes and n-1 edges with it's weight. There are two people A and B. I have been given a list of nodes of size k. A will pick a random node x from this list and B will ...
3
votes
1answer
1k views

Efficiently enumerating all paths from i to j of given length in a graph

I've been trying to efficiently solve this problem : given a integer p > 0 and a directed graph whose nodes are 0, ..., N-1, enumerate (not simply count) all the paths (not necessarily elementary) ...
2
votes
1answer
159 views

Suppose G is simple graph with n vertices. Prove that G has twice as many edges as vertices only if $n\geq 5$

I just didn't understand the second part of the prove "G has twice as many edges as vertices only "... what do I actually have to prove ? I understand it like $n=2e$ , is it right ? then isn't it's ...
31
votes
3answers
35k views

Algorithm that finds the number of simple paths from $s$ to $t$ in $G$

Can anyone suggest me a linear time algorithm that takes as input a directed acyclic graph $G=(V,E)$ and two vertices $s$ and $t$ and returns the number of simple paths from $s$ to $t$ in $G$. I have ...
13
votes
1answer
1k views

Are all MST minimum spanning trees reachable by Kruskal and Prim?

I believe this is true but have not been able to get a formal proof for either. But is it true that any minimum spanning tree is reachable by applying Kruskal's algorithm? Similarly, is this true for ...
9
votes
1answer
1k views

What is the most efficient algorithm and data structure for maintaining connected component information on a dynamic graph?

Say I have an undirected finite sparse graph, and need to be able to run the following queries efficiently: $IsConnected(N_1, N_2)$ - returns $T$ if there is a path between $N_1$ and $N_2$, otherwise ...
4
votes
1answer
1k views

Dijkstra's algorithm to compute shortest paths using k edges?

I am aware of using Bellman-Ford on a graph $G=(V,E)$ with no negative cycles to find the single-source single-destination shortest paths from source $s$ to target $t$ (both in $V$) using at most $k$ ...
3
votes
1answer
4k views

single algorithm to work on both directed and undirected graph to detect cycles?

I have been trying to implement an algorithm to detect cycles (probably how many of them) in a directed and undirected graph. That is the code should apply for both ...
10
votes
2answers
3k views

Why can't we find shortest paths with negative weights by just adding a constant so that all weights are positive?

I'm currently reading introduction to algorithms and came by Johnson’s algorithm that depends on making sure that all paths are positive. the algo depends on finding a new weight function (w') that ...
4
votes
2answers
1k views

Hamiltonian path in grid graph

Here is my situation. I have a grid-type graph with obstacles. Every move (horizontally, vertically or diagonally with a range of 1) has a cost of exactly 1 (the graph is not weighted) provided that ...
1
vote
2answers
185 views

Equivalent definition of minimal spanning tree

Prove that $T$ is MST $\Leftrightarrow$ for any edge $uv \notin T$, $uv$ has the maximal weight on the cycle created by adding $uv$ to $T$. It's my attempt to prove $\Rightarrow$: Consider the cycle ...
27
votes
2answers
3k views

Where to get graphs to test my search algorithms against?

I am implementing a set of path finding algorithms such as Dijkstra's, Depth First, etc. At first I used a couple of self made graphs, but now I'd like to take the challenge a bit further and thus I'...
12
votes
1answer
4k views

Getting parallel items in dependency resolution

I have implemented a topological sort based on the Wikipedia article which I'm using for dependency resolution, but it returns a linear list. What kind of algorithm can I use to find the independent ...
20
votes
2answers
27k views

Getting negative cycle using Bellman Ford

I have to find a negative cycle in a directed weighted graph. I know how the Bellman Ford algorithm works, and that it tells me if there is a reachable negative cycle. But it does not explicitly name ...
14
votes
2answers
2k views

Shortest non intersecting path for a graph embedded in a euclidean plane (2D)

What algorithm would you use to find the shortest path of a graph, which is embedded in an euclidean plane, such that the path should not contain any self-intersections (in the embedding)? For ...
32
votes
1answer
7k views

Do you get DFS if you change the queue to a stack in a BFS implementation?

Here is the standard pseudocode for breadth first search: ...
21
votes
1answer
957 views

How many shortest distances change when adding an edge to a graph?

Let $G=(V,E)$ be some complete, weighted, undirected graph. We construct a second graph $G'=(V, E')$ by adding edges one by one from $E$ to $E'$. We add $\Theta(|V|)$ edges to $G'$ in ...
27
votes
4answers
2k views

How to find a superstar in linear time?

Consider directed graphs. We call a node $v$ superstar if and only if no other node can be reached from it, but all other nodes have an edge to $v$. Formally: $\qquad \displaystyle $v$ \text{ ...
8
votes
0answers
142 views

Practical algorithms for the disjoint paths problem

Given an undirected graph $G$ and two pairs of vertices $(s_1, t_1), (s_2, t_2)$, the disjoint paths problem (DPP) asks for two vertex-disjoint paths, one from $s_1$ to $t_1$ and the other from $...
6
votes
2answers
6k views

Kosaraju’s Algorithm - why transpose? [duplicate]

In directed graph, to find strongly connected components why do we have to transpose adjacency matrix (reverses the direction of all edges) if we could use reversed list of nodes by they finishing ...
6
votes
2answers
685 views

Split-Find: maintaining dynamic graph connectivity information, under edge deletion

Is there a data structure to keep track of the connected components of a dynamic graph, when the graph might by changing by deleting edges of the graph? Let $G$ be an undirected graph. I have two ...
15
votes
3answers
1k views

How to approach Dynamic graph related problems

I asked this question at generic stackoverflow and I was directed here. It will be great if some one can explain how to approach partial or fully dynamic graph problems in general. For example: ...
9
votes
5answers
6k views

Converting a digraph to an undirected graph in a reversible way

I am looking for an algorithm to convert a digraph (directed graph) to an undirected graph in a reversible way, ie the digraph should be reconstructable if we are given the undirected graph. I ...
6
votes
2answers
3k views

Correctness of Strongly Connected Components algorithm for a directed graph

I have been reading up on algorithm for finding the strongly connected components in a directed graph $G=(V,E)$. It considers two DFS search and the second step is transposing the original graph $G^T$....
5
votes
1answer
311 views

Transition coverage for a DFA

Let $G$ be a directed graph, with a single source node $s$. I want to find a collection of paths that cover every edge of $G$ (i.e., every edge of $G$ appears in at least one of these paths), where ...
5
votes
1answer
3k views

Optimal algorithm to traverse all paths in the order of shortest path

I have to generate all possible paths in a directed, acyclic weighted graph with edge costs. I also have to sort them in order of shortest path. The simplest way that comes to mind is to do a depth-...
2
votes
2answers
66 views

Given all pairs shortest paths matrix, find graph with minimum total sum of edges

I was looking at some problems about graphs, and I got stuck on this one. Namely, we have given matrix of size $N \cdot N$ representing the length of the shortest path in undirected graph between some ...
4
votes
2answers
183 views

Why Djikstra's algorithm is said to have $\mathcal{O}(|V|^2)$ complexity?

Djikstra's algorithm assigns some number to non-removed vertex each time it finds a path from removed vertex to it. Number of assignments is $\mathcal{O}(|V|^2)$. However, complexity of assignment is ...
2
votes
2answers
394 views

Proving that finding wheel subgraphs is NP-complete

Can you help me with this problem ? Given an undirected graph $G$ and an integer $n$, prove that determining whether the graph has wheel on $n$ vertices $W_{n}$ (a wheel $W_{i}$ is such that $i$ ...
1
vote
1answer
126 views

lower bound proof with adversary argument

We have to run a song on a Walkman, for that we need 2 full batteries. Let's say we have a mixed set of 30 batteries (15 are empty and and 15 are full) and then only way to test if the battery is full ...
5
votes
1answer
517 views

NP-completeness of graph isomorphism through edge contractions with an edge validity condition

Given Graphs $G=(V_1,E_1)$ and $H=(V_2,E_2)$. Can a graph isomorphic to $H$ be obtained from $G$ by a sequence of edge contractions ? We know this problem is NP-complete. What about if only a subset ...
5
votes
3answers
267 views

Is it possible to reconstruct graph if we have given matrix of shortest pairs

I'm trying to reconstruct graph if we have given the result of floyd-warshall algorithm, more formally: Let's say we have given undirected weighted tree (graph without cycles) with $N$ nodes, such ...
4
votes
1answer
70 views

Connected components and graph edition

There are known algorithms to find the connected components of a given graph. Those I know are easily extensible to support addition of nodes and edges to the graph and then find the resulting ...
4
votes
3answers
6k views

Dijkstra's algorithm for undirected graphs with negative edges

INPUT: "an undirected, weighted graph (negative weights allowed)" Could someone give an example for an undirected graph with negative edges where Dijkstra's algorithm doesn't work? As far as i ...
4
votes
2answers
89 views

Karp hardness of searching for a matching cut

Follow-up question in the series: Karp hardness of searching for a matching erosion Karp hardness of searching for a matching split Maximum Matching Cut problem Input: An undirected graph $G(...
3
votes
1answer
73 views

Karp hardness of searching for a matching split

UPDATE: In 2 days, if no more convincing answer is posted, then bounty of 50 rep. will go to xskxzr. Due to lack of connectedness and a clean & clear cut, the bounty is still open for 2 days. (UTC ...
3
votes
1answer
37 views

Karp hardness of searching for a matching erosion

First, read the previous question: Karp hardness of searching for a matching cut As mentioned in the supposed-to-be-comment answer in that question, without the requirement of cardinality $k$, the ...
2
votes
1answer
1k views

How to find max flow in a graph after decrementing an edge capacity?

We're given a graph $G=(V, E)$, with source $s$ and sink $t$, $s\neq t$, and that all capacities are non-negative integers. Also the max flow itself is given, so we receive the value of max flow for ...