Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.
464
questions
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
9
votes
1
answer
967
views
How hard is finding the shortest path in a graph matching a given regular language?
Suppose we are given a directed graph $G = (V, E)$ with edge weights $w : E \rightarrow \mathbb{R}$ (we can assume there are no negative cycles) and edge labels $\ell : E \rightarrow \Sigma$ from some ...
- 3,473
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
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
6
votes
2
answers
3k
views
Does Ford-Fulkerson always produce the left-most min-cut
When using Ford-Fulkerson to find max-flow between s and t, the exact choice of flow-graph depends on which paths are found.
However, if you then use the left-over residual graph to produce a min-cut ...
- 416
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 ...
9
votes
1
answer
8k
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}$-...
- 6,191
2
votes
2
answers
828
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 ...
- 133
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
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
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
28
votes
3
answers
44k
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
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
14
votes
2
answers
10k
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 ...
- 243
14
votes
1
answer
7k
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 ...
- 243
7
votes
1
answer
7k
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 ...
- 71
6
votes
2
answers
1k
views
Finding a subset in bipartite graph violating Hall's condition
We are given a bipartite graph of $n \leq 200$ vertices in both the first and the second partite set. Let $U$ be some set of vertices in the first set, and $V$ those vertices from the second that are ...
- 187
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
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
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
8
votes
2
answers
10k
views
Updating an MST $T$ when the weight of an edge not in $T$ is decreased
Given an undirected, connected, weighted graph $G = (V,E,w)$ where $w$ is the weight function $w: E \to \mathbb{R}$ and a minimum spanning tree (MST) $T$ of $G$.
Now we decrease the weight by $k$ of ...
- 9,501
4
votes
2
answers
6k
views
What edges are not in any MST?
This is a homework question. I do not want the solution - I'm offering the solution I've been thinking of and wish to know whether is it good or why is it flawed.
Consider a weighted undirected graph....
- 149
3
votes
1
answer
2k
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) ...
- 33
3
votes
1
answer
658
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 ...
- 33
3
votes
1
answer
3k
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$ ...
- 411
2
votes
1
answer
6k
views
Number of Different AVL Tree
I studying the related question.
https://stackoverflow.com/questions/13500560/number-of-ways-to-create-an-avl-tree-with-n-nodes-and-l-leaf-node
but it's not so general.
In-fact, We want to know ...
- 507
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
15
votes
1
answer
18k
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 ...
- 255
14
votes
2
answers
8k
views
Proving a binary tree has at most $\lceil n/2 \rceil$ leaves
I'm trying to prove that a binary tree with $n$ nodes has at most $\left\lceil \frac{n}{2} \right\rceil$ leaves. How would I go about doing this with induction?
For people who were following in the ...
- 453
12
votes
2
answers
4k
views
Graph isomorphism problem for labeled graphs
In the case of unlabeled graphs, the graph isomorphism problem can be tackled by a number of algorithms which perform very well in practice. That is, although the worst case running time is ...
- 121
10
votes
2
answers
542
views
Peer grading design - choosing a graph, to get accurate rankings/ratings
Background. I am writing some code for semi-automated grading, using peer grading as part of the grading process. Students are given pairs of essays at a time, and the students have a slider to choose ...
- 203
10
votes
4
answers
1k
views
Recovering a point embedding from a graph with edges weighted by point distance
Suppose I give you an undirected graph with weighted edges, and tell you that each node corresponds to a point in 3d space. Whenever there's an edge between two nodes, the weight of the edge is the ...
- 5,802
9
votes
1
answer
7k
views
Minimum-cut with minimum number of edges
I am sure many folks here know the famous min-cut max-flow theorem - the capacity of the minimum cut is equal to the maximum flow from a given source, s, to a given sink, t, in a graph.
Firstly, let'...
- 255
7
votes
2
answers
4k
views
Example of graph with exponential many s-t minpaths and min cuts
I am trying to find a graph in which both s-t minpaths and min cuts are exponential.
Individually I found examples in which s-t minpaths and s-t min cuts are exponential. Can some one provide me an ...
- 367
7
votes
2
answers
19k
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 ...
- 203
6
votes
2
answers
9k
views
How to find spanning tree of a graph that minimizes the maximum edge weight?
Suppose we have a graph G. How can we find a spanning tree that minimizes the maximum weight of all the edges in the tree? I am convinced that by simply finding an MST of G would suffice, but I am ...
- 1,121
4
votes
1
answer
325
views
Between every two MST's there's a series of "nearby" MST's
Given undirected connected graph $G=(V,E)$ and a weight function $w:E\to\mathbb{R}$, two MST's $T_1, T_2$ are nearby if there exists $e\in T, e'\in T'$ such that $T'=(T-\{e\})\cup\{e'\}$.
Prove that ...
- 327
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
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
17
votes
1
answer
6k
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 ...
- 273
15
votes
1
answer
4k
views
$O(n^{k-1}$) algorithm for K-clique problem
Clique problem is a well known $NP$-complete problem where the size of the required clique is part of the input. However, k-clique problem has a trivial polynomial time algorithm ($O(n^k)$ when $k$ is ...
- 4,417
14
votes
2
answers
1k
views
Efficiently sampling shortest $s$-$t$ paths uniformly and independently at random
Let $G$ be a graph, and let $s$ and $t$ be two vertices of $G$. Can we efficiently sample a shortest $s$-$t$ path uniformly and independently at random from the set of all shortest paths between $s$ ...
- 22.5k
10
votes
1
answer
2k
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 ...
- 1,720
9
votes
1
answer
10k
views
Effect of increasing the capacity of an edge in a flow network with known max flow
I need your help with an exercise on Ford-Fulkerson.
Suppose you are given a flow network with capacities $(G,s,t)$ and you are also given the max flow $|f|$ in advance.
Now suppose you are given an ...
- 237
8
votes
2
answers
1k
views
SAT algorithm for determining if a graph is disjoint
What are some good algorithms to have a SAT (CNF) solver determine if a given graph is fully-connected or disjoint?
The best one I can think of is this:
Number the nodes 1..N, where N is the number ...
- 203
8
votes
5
answers
32k
views
Every simple undirected graph with more than $(n-1)(n-2)/2$ edges is connected
If a graph with $n$ vertices has more than $\frac{(n-1)(n-2)}{2}$ edges then it is connected.
I am a bit confused about this question, since I can always prove that for a graph to connected you need ...
- 1,027
8
votes
0
answers
250
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 $...
- 81
7
votes
1
answer
6k
views
How to find the maximum independent set of a directed graph?
I'm trying to solve this problem.
Problem: Given $n$ positive integers, your task is to select a maximum number of integers so that there are no two numbers $a, b$ in which $a$ is divisible by $b$...
- 255
5
votes
2
answers
5k
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 ...
- 269