Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.
4,856
questions
85
votes
8
answers
59k
views
Graph searching: Breadth-first vs. depth-first
When searching graphs, there are two easy algorithms: breadth-first and depth-first (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)).
Now, are ...
- 975
61
votes
5
answers
14k
views
Is zero allowed as an edge's weight, in a weighted graph?
I am trying to write a script that generates random graphs and I need to know if an edge in a weighted graph can have the 0 value.
actually it makes sense that 0 could be used as an edge's weight, ...
- 729
50
votes
3
answers
79k
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 ...
- 1,219
47
votes
4
answers
65k
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'$.
...
- 1,269
43
votes
1
answer
11k
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:
...
- 1,326
41
votes
9
answers
62k
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 ...
- 521
39
votes
14
answers
13k
views
What are some real world applications of graphs?
Can you give some real world examples of what graphs algorithms people are actually using in applications?
Given a complicated graphs, say social networks, what properties/quantity people want to ...
- 568
39
votes
4
answers
54k
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 ...
- 899
37
votes
0
answers
667
views
Finding an $st$-path in a planar graph which is adjacent to the fewest number of faces
I am curious whether the following problems has been studied before, but wasn't able to find any papers about it:
Given a planar graph $G$, and two vertices $s$ and $t$, find an
$s$-$t$ path $P$ ...
- 371
35
votes
5
answers
8k
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$ ...
D.W.♦
- 156k
31
votes
2
answers
42k
views
Is Dijkstra's algorithm just BFS with a priority queue?
According to this page, Dijkstra's algorithm is just BFS with a priority queue. Is it really that simple? I think not.
- 755
30
votes
1
answer
12k
views
How hard is counting the number of simple paths between two nodes in a directed graph?
There is an easy polynomial algorithm to decide whether there is a path between two nodes in a directed graph (just do a routine graph traversal with, say, depth-first-search).
However it seems that, ...
- 1,379
30
votes
1
answer
981
views
Graph problem known to be $NP$-complete only under Cook reduction
The theory of NP-completeness was initially built on Cook (polynomial-time Turing) reductions. Later, Karp introduced polynomial-time many-to-one reductions. A Cook reduction is more powerful than a ...
- 4,417
29
votes
4
answers
42k
views
The time complexity of finding the diameter of a graph
What is the time complexity of finding the diameter of a graph
$G=(V,E)$?
${O}(|V|^2)$
${O}(|V|^2+|V| \cdot |E|)$
${O}(|V|^2\cdot |E|)$
${O}(|V|\cdot |E|^2)$
The diameter of a ...
- 2,193
29
votes
1
answer
20k
views
Is the k-clique problem NP-complete?
In this Wikipedia article about the Clique problem in graph theory it states in the beginning that the problem of finding a clique of size K, in a graph G is NP-complete:
Cliques have also been ...
Eivind
29
votes
2
answers
6k
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'...
- 600
28
votes
3
answers
14k
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 ...
28
votes
4
answers
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{ ...
- 72k
28
votes
7
answers
79k
views
Why can't DFS be used to find shortest paths in unweighted graphs?
I understand that using DFS "as is" will not find a shortest path in an unweighted graph.
But why is tweaking DFS to allow it to find shortest paths in unweighted graphs such a hopeless prospect? ...
- 1,783
28
votes
3
answers
45k
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 ...
- 467
28
votes
2
answers
607
views
How to efficiently determine whether a given ladder is valid?
At my local squash club, there is a ladder which works as follows.
At the beginning of the season we construct a table with the name of each
member of the club on a separate line.
We then write the ...
- 399
26
votes
4
answers
17k
views
Finding the minimum cut of an undirected graph
Here's a question from a past exam I'm trying to solve:
For an undirected graph $G$ with positive weights $w(e) \geq 0$, I'm trying to find the minimum cut. I don't know other ways of doing that ...
- 1,697
25
votes
7
answers
5k
views
Do any two spanning trees of a simple graph always have some common edges?
I tried few cases and found any two spanning tree of a simple graph has some common edges. I mean I couldn't find any counter example so far. But I couldn't prove or disprove this either. How to ...
- 1,293
25
votes
3
answers
31k
views
What is the fastest algorithm for finding all shortest paths in a sparse graph?
In an unweighted, undirected graph with $V$ vertices and $E$ edges such that $2V \gt E$, what is the fastest way to find all shortest paths in a graph? Can it be done in faster than Floyd-Warshall ...
- 361
25
votes
2
answers
63k
views
Residual Graph in Maximum Flow
I am reading about the Maximum Flow Problem here. I could not understand the intuition behind the Residual Graph. Why are we considering back edges while calculating the flow?
Can anyone help me ...
- 251
25
votes
4
answers
49k
views
Am I right about the differences between Floyd-Warshall, Dijkstra and Bellman-Ford algorithms?
I've been studying the three and I'm stating my inferences from them below. Could someone tell me if I have understood them accurately enough or not? Thank you.
Dijkstra algorithm is used only when ...
Programming Noob
25
votes
1
answer
5k
views
Is there an efficient algorithm for this vertex cycle cover problem?
I've been trying to find an algorithm to find a maximum vertex cycle cover of a directed graph $G$ — that is, a set of disjoint cycles which contain all the vertices in $G$, with as many cycles as ...
- 633
25
votes
2
answers
3k
views
Is Logical Min-Cut NP-Complete?
Logical Min Cut (LMC) problem definition
Suppose that $G = (V, E)$ is an unweighted digraph, $s$ and $t$ are two vertices of $V$, and $t$ is reachable from $s$. The LMC Problem studies how we can ...
- 401
24
votes
5
answers
14k
views
The purpose of grey node in graph depth-first search
In many implementations of depth-first search that I saw (for example: here), the code distinguish between a grey vertex (discovered, but not all of its neighbours was visited) and a black vertex (...
- 343
24
votes
2
answers
36k
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 ...
- 619
23
votes
5
answers
5k
views
Assuming P = NP, how would one solve the graph coloring problem in polynomial time?
Assuming we have $\sf P = NP$, how would I show how to solve the graph coloring problem in polynomial time?
Given a graph $G = (V,E)$, find a valid coloring $\chi(G) : V \to \{1,2,\cdots,k\}$ for ...
- 352
23
votes
3
answers
42k
views
When are adjacency lists or matrices the better choice?
I was told that we would use a list if the graph is sparse and a matrix if the graph is dense. For me, it's just a raw definition. I don't see much beyond it. Can you clarify when would it be the ...
- 351
23
votes
2
answers
8k
views
NP completeness proof of a spanning tree problem
I am looking for some hints in a question asked by my instructor.
So I just figured out this decision problem is $\sf{NP\text{-}complete}$:
In a graph $G$, is there a spanning tree in $G$ that ...
- 333
22
votes
1
answer
2k
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 ...
- 9,036
22
votes
1
answer
547
views
Approximate minimum-weighted tree decomposition on complete graphs
Say I have a weighted undirected complete graph $G = (V, E)$. Each edge $e = (u, v, w)$ is assigned with a positive weight $w$. I want to calculate the minimum-weighted $(d, h)$-tree-decomposition. By ...
- 321
21
votes
9
answers
10k
views
Is Group Theory useful in Computer Science in areas other than cryptography?
I have heard many times that Group Theory is highly important in Computer Science, but does it have any use other than cryptography? I tend to believe that it does have many other usages, but cannot ...
- 161
21
votes
4
answers
8k
views
Why are directed graphs important?
We have been reading about algorithms for MST, strong-connectivity, routing, etc. in directed graphs.
Also recently people have been doing research for dynamic and fault tolerant algorithms for ...
- 464
21
votes
5
answers
52k
views
What is the significance of negative weight edges in a graph?
I was doing dynamic programming exercises and found the Floyd-Warshall algorithm. Apparently it finds all-pairs shortest paths for a graph which can have negative weight edges, but no negative cycles.
...
- 377
21
votes
2
answers
15k
views
Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?
If a weighted graph $G$ has two different minimum spanning trees $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$, then is it true that for any edge $e$ in $E_1$, the number of edges in $E_1$ with the same ...
- 1,121
21
votes
1
answer
1k
views
Generating inputs for random-testing graph algorithms?
When testing algorithms, a common approach is random testing: generate a significant number of inputs according to some distribution (usually uniform), run the algorithm on them and verify correctness....
- 72k
21
votes
2
answers
862
views
Finding at least two paths of same length in a directed graph
Suppose we have a directed graph $G=(V,E)$ and two nodes $A$ and $B$.
I would like to know if there are already algorithms for calculating the following decision problem:
Are there at least two ...
- 351
20
votes
6
answers
5k
views
Real life examples of negative weight edges in graphs
I am unable to relate to any real life examples of negative weight edges in graphs. Distances between cities cannot be negative. Time taken to travel from one point to another cannot be negative. ...
- 337
20
votes
1
answer
20k
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 ...
- 2,189
20
votes
2
answers
2k
views
Are link-cut trees ever used in practice, for max flow computation or other applications?
Many max flow algorithms that I commonly see implemented, Dinic's algorithm, push relabel, and others, can have their asymptotic time cost improved through the use of dynamic trees (also known as link-...
- 301
20
votes
1
answer
974
views
Optimal algorithm for finding the girth of a sparse graph?
I wonder how to find the girth of a sparse undirected graph. By sparse I mean $|E|=O(|V|)$. By optimum I mean the lowest time complexity.
I thought about some modification on Tarjan's algorithm for ...
user742
20
votes
1
answer
2k
views
Could min cut be easier than network flow?
Thanks to the max-flow min-cut theorem, we know that we can use any algorithm to compute a maximum flow in a network graph to compute a $(s,t)$-min-cut. Therefore, the complexity of computing a ...
D.W.♦
- 156k
19
votes
3
answers
72k
views
Difference between cross edges and forward edges in a DFT
In a depth first tree, there are the edges define the tree (i.e the edges that were used in the traversal).
There are some leftover edges connecting some of the other nodes. What is the difference ...
- 1,133
19
votes
2
answers
21k
views
Shortest Path on an Undirected Graph?
So I thought this (though somewhat basic) question belonged here:
Say I have a graph of size 100 nodes arrayed in a 10x10 pattern (think chessboard). The graph is undirected, and unweighted. Moving ...
- 487
19
votes
5
answers
19k
views
Maximum Independent Set of a Bipartite Graph
I'm trying to find the Maximum Independent Set of a Biparite Graph.
I found the following in some notes "May 13, 1998 - University of Washington - CSE 521 - Applications of network flow":
Problem:
...
- 709
19
votes
2
answers
469
views
How many edges can a unipathic graph have?
A unipathic graph is a directed graph such that there is at most one simple path from any one vertex to any other vertex.
Unipathic graphs can have cycles. For example, a doubly linked list (not a ...
