More graph Algos

Question 1

Forest

Answer 1

is an undirected, disconnected, acyclic graph. In other words, a disjoint collection of trees

Question 2

Kruskal’s algo for a connected (+ edge weighted + undirected) graph does what?

Answer 2

Finds a minimum spanning tree

Question 3

Is kruskals greedy or Non greedy

Answer 3

Greedy

Question 4

What is a spanning tree?

Answer 4

(Pertains to undirected graphs). a subgraph that is a tree which includes all of the vertices of The graph

Question 5

Prim’s algo benefits vs other MST algos

Answer 5

for graphs that are sufficiently dense, Prim’s algorithm can be made to run in linear time, meeting or improving the time bounds for other algorithms.

Question 6

List the three basic greedy algorithms to find an MST

Answer 6

Prim’s (Jarnik’s), Kruskal’s, Borůvka’s (Sollin’s) algorithms

Question 7

Kruskals

Answer 7

create a forest F (a set of trees), where each vertex in the graph is a separate tree
create a set S containing all the edges in the graph
while S is nonempty and F is not yet spanning
remove an edge with minimum weight from S
if the removed edge connects two different trees then add it to the forest F, combining two trees into a single tree
At the termination of the algorithm, the forest forms a minimum spanning forest of the graph. If the graph is connected, the forest has a single component and forms a minimum spanning tree.

Question 8

Topological sort definition

Answer 8

a linear ordering of a graph’s vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

Question 9

Canonical use case of topological sort

Answer 9

in scheduling a sequence of jobs or tasks based on their dependencies. The jobs are represented by vertices, and there is an edge from x to y if job x must be completed before job y can be started (for example, when washing clothes, the washing machine must finish before we put the clothes in the dryer)

Question 10

List names of Topological sort implementations - Kahn, Tarjan’s DFS solution, PRAM with adjacency matrix squaring, parallelized Khan with a distributed memory machine

Answer 10

Kahn, Tarjan (DFS), adjacency matrix squaring on a PRAM, parallelized Kahn on a distributed memory machine

Question 11

High level how to quickly compute shortest path thru weighted directed a cyclic graph

Answer 11

Use topological sort

Question 12

Low level implementation of finding shortest paths on directed acyclic weighted graph

Answer 12

…

Question 13

When are topological ordering a impossible

Answer 13

When there are cycles

Question 14

DAG

Answer 14

Directed acyclic graph

Question 15

Known Time complexity of finding a topological sorting of a DAG

Answer 15

O(n)

Question 16

FAS stands for

Answer 16

Feedback Arc Set

Question 17

Feedback Arc set is aka

Answer 17

Feedback Edge Set

Question 18

Feedback arc set

Answer 18

set of edges which, when removed from the graph, leaves an acyclic graph. Put another way, it is a set containing at least one edge of every cycle in the graph.

Question 19

What algorithm do you use to find shortest path from a source to all vertices?

Answer 19

Djikstra’s

Question 20

Algo name for shortest path from every vertex to every other vertex

Answer 20

Floyd Marshall

Question 21

Memory complexity of sum of length of all adjacency lists for directed graph vs undirected graph

Answer 21

|E| vs 2|E|

Question 22

For both directed and undirected graphs the memory complexity of the adjacency list representation is

Answer 22

O(V + E)

Question 23

disadvantage of adjacency-list representation for edges

Answer 23

there is no quicker way to determine if a given edge (u, v) is present in the graph than to search for v in the adjacency list Adj[u]. which worst case could be O(V) if u is connected to all vertices

Question 24

List and compare two alternatives to adjacency lists to represent edges

Answer 24

1) have Adj[u] be a hash table containing the vertices v for which (u, v) ∈ E. Expected time is O(1). Worst case time is O(V) (if you get a lot of hash collisions (but is that really even likely???)). 2) have Adj[u] be an array that you sort and then during look-up you perform binary search for an expected and worst case time of O(lg V)`

Question 25

Djikstra binary heap implementation time complexity

Answer 25

Theta((|E|+|V|)log|V|) time complexity,

Question 26

Djikstras does what?

Answer 26

Finds the shortest path to every node in the (weighted-edge) graph from a single source

Question 27

Bellman Ford does what?

Answer 27

Similar to Dijkstra’s algorithm, the Bellman-Ford algorithm 1)works to find the shortest path between a given node and all other nodes in the graph. Though it is 2)slower than the former, Bellman-Ford makes up for its a disadvantage with its versatility. Unlike Dijkstra’s algorithm, Bellman-Ford is capable of 3) handling graphs in which some of the edge weights are negative. 4) It’s important to note that if there is a negative cycle – in which the edges sum to a negative value – in the graph, then there is no shortest or cheapest path. Meaning the algorithm is prevented from being able to find the correct route since it terminates on a negative cycle. 5)Bellman-Ford is able to detect negative cycles and report on their existence.

Question 28

Floyd Marshal does what?

Answer 28

The Floyd-Warshall stands out in that unlike djikstra and bellman Ford it is not a single-source algorithm. Meaning, it calculates the shortest distance between every pair of nodes in the graph, rather than only calculating from a single node

Question 29

What is Floyd marshal very useful for?

Answer 29

when it comes to generating routes for multi-stop trips as it calculates the shortest path between all the relevant nodes. For this reason, many route planning software’ will utilize this algorithm as it will provide you with the most optimized route from any given location. Therefore, no matter where you currently are, Floyd-Warshall will determine the fastest way to get to any other node on the graph.

Question 30

Johnson’s algorithm works best when?

Answer 30

With sparse graphs

Question 31

Can Floyd warshal detect the presence of a negative weight cycle ?

Answer 31

Yes

Question 32

How does Floyd warshal detect the presence of a negative weight cycle?

Answer 32

...

Question 33

Floyd warshal time complexity

Answer 33

O(V^3)

Question 34

Johnson’s runtime complexity

Answer 34

O(V^2 * logV + |V||E|)

Question 35

How does Iohnsons work high level?

Answer 35

it uses two other shortest path algorithms as subroutines. It uses Bellman-Ford in order to reweight the input graph to eliminate negative edges and detect negative cycles. With this new, altered graph, it then uses Dijkstra's shortest path algorithm to calculate the shortest path between all pairs of vertices. The output of the algorithm is then the set of shortest paths in the original graph.

Question 36

Bellman-Ford time complexity

Answer 36

O(VE)

Question 37

Djikstra Fibonacci heap time complexity

Answer 37

O(|E|+|V|log| V|)

Question 38

In graphs how does the time complexity w.r.t E relate to V

Answer 38

E in worst case is V^2

Question 39

What complexity class is determining whether a certain edge is in the MST?

Answer 39

P

Question 40

What complexity class is determining whether a total weight (of an MST) exceeds a certain value?

Answer 40

P

Question 41

MST

Answer 41

minimum spanning tree

Question 42

What is considered a dense graph?

Answer 42

|E|/|V| > log log log |V|

Question 43

what is the dynamic MST problem

Answer 43

concerns the update of a previously computed MST after an edge weight change in the original graph or the insertion/deletion of a vertex

Question 44

maximum spanning tree

Answer 44

a spanning tree with weight greater than or equal to the weight of every other spanning tree

Question 45

how to find a maximum spanning tree?

Answer 45

Such a tree can be found with algorithms such as Prim's or Kruskal's after multiplying the edge weights by -1 and solving the MST problem on the new grap

Question 46

The degree constrained minimum spanning tree

Answer 46

a minimum spanning tree in which each vertex is connected to no more than d other vertices, for some given number d.

Question 47

The capacitated minimum spanning tree

Answer 47

a tree that has a marked node (origin, or root) and each of the subtrees attached to the node contains no more than a c nodes. c is called a tree capacity.

Question 48

Steiner tree problem

Answer 48

the problem of finding a minimum tree that spans the given subset of vertices (aka the terminals). this minimum tree may contain vertices that were not provided as terminals

Question 49

What does Tarjan’s algorithm do?

Answer 49

an efficient graph algorithm to find the strongly connected components in a directed graph in linear time by utilizing Depth First Search traversal of a graph

Question 50

SCCs

Answer 50

Strongly connected components

Question 51

Strongly connected meaning

Answer 51

A directed graph is called strongly connected if there is a path in each direction between each pair of vertices of the graph. That is, a path exists from the first vertex in the pair to the second, and another path exists from the second vertex to the first (of course the path can be more than one edge long). Equivalently, a strongly connected component of a directed graph G is a subgraph that is strongly connected, and is maximal with this property: no additional edges or vertices from G can be included in the subgraph without breaking its property of being strongly connected.

Question 52

Daniel Larkin 2014

Answer 52

They concluded that d-ary heaps such as binary heaps are faster than all other heap implementations when the decrease-key operation is not needed (and hence there is no need to externally track the location of nodes in the heap), but that when decrease-key is needed pairing heaps are often faster than d-ary heaps and almost always faster than other pointer-based heaps, including data structures like Fibonacci heaps that are theoretically more efficient. [is this conclusion just for djikstras? Or heaps in general?]

Question 53

Mo Chen 2007

Answer 53

examined priority queues specifically for use with Dijkstra's algorithm and concluded that in normal cases using a d-ary heap without decrease-key (instead duplicating nodes on the heap and ignoring redundant instances) resulted in better performance, despite the inferior theoretical performance guarantees.

Question 54

Djikstras implementation w PQ w decreaseKey

Answer 54

Djikstra(adj, s){ // s = sourceKey ``` Dist = new PQ() keys = Object.keys(adj) For (let i = 0; i < keys.length; i ++) { key = keys[i] dist.insert(key, NUMBER.MAX_SAFE_INTEGER) Unvisited.push(keys[i]) } ``` Dist.decreaseKey(s,0) While(x = dist.extractMin()){ ``` Neighbors = adj[x] For(let i =0; I < neighbors.length;I++){ n = neighbors[i] if (dist.get(x) + n.weight < dist[n.label]) { dist[n.label] = dist[x] + n.weight Path[n.label] = x } } ```

Question 55

Djiksyra with priority queue verbal explanation

Answer 55

You should use priority queue where the vertex with the shortest distance from the starting vertex will get the highest priority. Initially, all vertices will have the shortest distance of infinity and the starting vertex will have the shortest distance 0. Start by inserting of all vertices (with its edges) from the graph inside the PQ. Remove vertex from the PQ and explore all its edges. Compare the shortest distances with all adjacent vertices and if any distance is less than the shortest distance on the current vertex, update adjacent vertex shortest distance inside the PQ. Continue while PQ is not empty. Vertices which have no edges will finish with the shortest distance of infinity because it is not possible 'get to them' from the starting vertex. However, they will be still removed from the PQ.

Question 56

What happens if you don’t relax the edges of the unvisited node that has the least distance of all the unvisited nodes?

Answer 56

I’m not sure. I think it breaks some loop invariant that the logic of djikstra depends on. I’m not sure of the exact nature of the incorrect output that would result, but i might test it out one of these days

Question 57

What is a simple way to emulate the behavior of the decrease-key operation of a priority queue without actually implementing such a method?

Answer 57

(Used in djikstra’s) To decrease the key of a node, just insert that node again in the pq, such that there are now 2+ nodes with the same key in the queue, but such that the node with such key and the lowest value will now in the future be popped first from the queue When popping (aka polling) nodes from the queue, when a node is polled, as part of preprocessing you add that key to a “visited” list, and in the future when polling nodes, if the polled node’s key already exists in the visited list, you skip processing that node and poll the next node to preprocess+process it

Question 58

Speed of prim's vs kruskal's vs Boruvka's algorithm's?

Answer 58

equally asymptotically fast for sparse graphs, but slower than algorithms; Prim's can be made to run in linear time on dense graphs

Question 59

SoftHeap

Answer 59

a kind of priority queue that gives us an optimal | trade-off between accuracy and speed.

Question 60

Pettie's "contractibility"

Answer 60

A subgraph C is said to be DJP-contractible with respect to G if after executing the DJP algorithm on G for some number of steps, with a suitable start vertex in C, the tree that results is a spanning tree for C. [ https://www.cs.utexas.edu/~vlr/papers/optmsf-jacm.pdf]

Question 61

How can one provably identify edges in the MSF? How can one provably identify edges NOT in the MSF?

Answer 61

by using the cut property; by using the cycle property

Question 62

The cut property states

Answer 62

that the lightest edge crossing any partition of the vertex set into two parts must belong to the MSF.

Question 63

the cycle property states

Answer 63

that the heaviest edge in any cycle in the graph cannot be in the MSF.

Question 64

contracting in graphs

Answer 64

https://www.cs.utexas.edu/~vlr/papers/optmsf-jacm.pdf

Question 65

nominal density of a graph

Answer 65

(during contraction - e.g. in Pettie's algorithm) y is the ratio m/n', where m, as usual, is the number of edges in the original graph, and n' is the number of vertices in the current graph [https://www.cs.utexas.edu/~vlr/papers/optmsf-jacm.pdf]

Question 66

How to find a cycle in a directed graph?

Answer 66

Technique 1 (using colors). Use enum WHITE|GRAY|BLACK or UNVISITED | VISITING | VISITED Do DFS: hasCycle(n, adj, nodes) { visiting[n.label] = true // use separate data structure if you can’t just add properties on the node itself ``` for (let child of adj[n.label]) { if (visiting[child.label]) { return true // if the connection to this child itself forms a cycle return true } else { // or if any grandchildren+ forms a cycle if (hasCycle(nodes[sister.label], adj, nodes)) { //)) return true } } return false } ``` } ——- Technique 2 ``` //doesn’t check if this node forms a particular cycle, but rather if one of its neighbors or neighbors’ neighbors forms the cycle (I guess taking into account the history of the path we are doing) function hasCycle(n, adj, path: SearchableStack) { ``` path.push(n.label) for (let x of adj[n]) { if (path.contains(n.label)) {

Question 67

SPFA aka

Answer 67

Shortest Path Faster Algorithm

Question 68

SPFA is an improvement of what algorithm

Answer 68

Bellman Ford; it is queue optimized Bellman Ford

Question 69

SPFA is believed to work well when?

Answer 69

random sparse graphs and is particularly suitable for graphs that contain negative-weight edges

Question 70

SPFA worst case running time

Answer 70

O(|V| |E|), same as Bellman Ford’s

Question 71

SPFA average runtime

Answer 71

Experiments suggest that the average running time is O(|E|) , and indeed this is true on random graphs, but it is possible to construct sparse graphs where SPFA runs in time Omega (|V|^{2})} like the usual Bellman-Ford algorithm

Question 72

Dual priority queue version of djikstra’s performance

Answer 72

has a significant overhead in the constant factor, and hence is quite slow in in-core execution, though it performs by far the best on sparse graphs out-of-core. [mo Chen 2007]

Question 73

IDM PQ

Answer 73

A priority queue that only supports insert and delete-min, as opposed to also supporting decrease-key

Question 74

A DK PQ

Answer 74

A priority queue that includes a decrease key operation

Question 75

A second alternative to a DK PQ

Answer 75

If there is no explicit decrease key operation, if you have access to a find operation you can find, remove, and then add again.

Question 76

How does djikstra algorithm work/perform correctly when it is used with a priority queue that doesn’t have a decrease key operation?

Answer 76

When you pop the min node x from the priority queue, you process it. Part of it is adding any of x’s neighbors to the priority queue if the path for that neighbor n thru x has a smaller weight (aka cost) than n used to have. Now there are two categories of questions that you may have: 1) what if node C was added to the PQ with weight 10 ( A->C=10) but then was also added to the PQ again with (A->B=4, B->C=4) giving it a better candidate weight of 8. Since node C is now in the queue twice, is the algorithm still going to function correctly? Well, to make sure it still functions correctly, you need to mark nodes visited when they are removed from the priority queue, and never do the processing on a node being removed that has already been visited. This works because of the following lemma/loop invariant: The shortest path P from A to Z when using this algorithm will always be fully traversed (where traversed is as defined as Z being REMOVED from the priority queue with the weight corresponding to what it would be if Zs weight was calculated when visiting from Z.prev (in path P) before any other longer paths from A to Z get processed. That is because always the node with the least weight is getting removed from the queue, so paths with the least weight are always getting traversed first, meaning if a node has multiple partially traversed paths constructed for it (where partially traversed means node Z is in the queue but not yet removed), the first path that is fully traversed will be the one with the lowest weight.

Question 77

The important difference between Boruvka's algorithm and Kruskal's or Prim's is that

Answer 77

with Boruvka's you don't need to presort the edges or maintain a priority queue.

Question 78

Both prims and boruvka are based on what observation?

Answer 78

the observation that if the edge costs are unique, the cheapest edge of any cut belongs to the spanning tree