How Graphs and Graph algorithms are treated

Question 1

For the class, what are the black box algorithms available for me? Are we allowed to change or modify?

Answer 1

A graph theory problem is a form of reduction. You are given some problem to solve, and the challenge is to solve that problem by using one of the graph algorithms we study this semester. In other words, you reduce your problem to a graph problem such that a known algorithm can solve it for you.

Algorithms:
- DFS
- BFS
- Dijkstra’s
- Belman-Ford
- Floyd-Warshall
- SCC
- Kruskal’s
- Prim’s
- Ford-Fulkerson
- Edmond’s-Karp
- 2-SAT

Not allowed to change ore modify the blackbox graph algorithm

Question 2

When answering for the designing an algorithm for graphs, what do you need to cover per section? Algorithm, justification, runtime?

Answer 2

Algorithm:
- NO PSEUDOCODE - use words

What changes you may need for the input

What black box you will feed your input to

What changes you may need for the output

Repeat with more black boxes as needed

Justification:
- Explain how your problem is solved by the black boxes used

• Explain how changing the inputs and/or outputs gets what you want

Analyze the runtime:
- Must be presented in Big O notation

• Can explain/analyze in words
• Can use known black box runtime without explanation. Must include run time analysis for any pre/post processing, as well as any modifications to the black box (if permitted by the problem)
• Again, if we give you a run time, you must meet that for full credit. If we do not specify a run time, faster (and correct) in Big O notation are worth more credit

Question 3

Explain how DFS is treated. What is the subroutine?

Answer 3

outputs connected components, topological sort on a DAG.

You also have access to the prev, pre and post arrays.

example)
vertex: [A, B, C, D, E, F, G, H]

pre: [2, 1, 12, 3, 4, 13, 5, 8]

post: [11, 16, 15, 10, 7, 14, 6, 9]

prev: [B, 0, B, A, D, C, E, D]

visited: [True, True, True, True, True, True, True, True]

For undirected graphs:
ccnum: [1, 1, 1, 2, 2, 3, 4, 4]

determines the connected components of a graph

(using alphabetical ordering again for simplicity). the connected component numbers are the pieces the graph is split into, and the array ccnum for DFS returns what numbered piece each vertex is in

Only use ccnum for undirected graphs

Explore is the subroutine

Question 4

Explain how BFS is treated

Answer 4

performs a breadth-first search of the graph from a starting vertex, provides dist array.

Question 5

Explain how Dijkstra’s algorithm is treated

Answer 5

find the shortest distance from a source vertex to all other vertices and a path can be recovered backtracking over the prev labels

Question 6

Which 2 algorithms can be used to compute the shortest path when weights are allowed to be negative?

Answer 6

Bellman-Ford

Floyd-Warshall

Question 7

Explain how SCC algorithm is treated

Answer 7

outputs the strongly connected components, and the metagraph of connected components.

Question 8

Which algorithms are used to find the MST?

Answer 8

Kruskal’s and Prim’s

Question 9

Which algorithms are used to find the max-flow of networks?

Answer 9

Ford-Fulkerson

Edmond’s-Karp

Question 10

Explain how 2-SAT algorithm is treated

Answer 10

takes a CNF with all clauses of size ≤ 2 and returns a satisfying assignment if it exists

Question 11

What are the assumptions about graphs in this class?

Answer 11

• simple graphs unless the problem states otherwise
  (no multi-edges or self-loops present)
• connected or disconnected
• undirected or directed
• When working with MSTs we assume the graph is both connected and undirected
• When working with flow networks we assume the graph is both connected and directed.
• we use adjacency lists for graphs in the class
  -> An array of vertices that are pointers to linked lists of adjacent vertices
  -> So each element in the list represents an edge to another vertex.

Assume ALL graphs in this class (input or your own) are labeled in such a way that they can be found by an index into the array.

Prefer to work with
We assume n = number of vertices and m = number of edges. We prefer O(n), O(m), O(n+m)

Question 12

Runtime for Traversing, reversing, copying, subgraphing, or otherwise working with a full graph:

Answer 12

O(n+m)

Question 13

Runtime for Checking, reading, or removing one vertex

Answer 13

O(1)

Question 14

Runtime for Iterating, checking, reading, removing, or otherwise working on all vertices (or subset):

Answer 14

O(n)

Question 15

Runtime for Checking, reading, or removing one edge

Answer 15

O(n) or O(m)

One is usually more correct than the other depending on what you are doing, but for the sake of simplicity, we will accept either when a single edge is involved

Question 16

Runtime Iterating, checking, reading, removing, or otherwise working on all edges (or subset)

Answer 16

O(n+m)

If you are working on all edges, you will need to check all vertices for its edges

Question 17

When you KNOW the graph is connected, either because we tell you or it is an MST or Max Flow problem where being connected is a given

Answer 17

We simplify O(n+m) to O(m)

Question 18

What is the ccnum in a DFS output?

Answer 18

“ccnum” is an array returned by DFS which tells us the connected component number of every vertex. “cc” is a counter used within DFS to determine which connected component number the algorithm is on and should currently set the vertices to. The “cc” counter only moves up one if there are more vertices left to visit after fully exploring from a particular vertex.

We don’t utilize connected component numbers in directed graphs

Question 19

What is the explore function in DFS?

Answer 19

TLDR: Explore will get you the list of vertices that s can reach in the visited array. This is specific to Explore without any additional details

Background: Explore and DFS often gets used interchangeably in other material. However, this class allows explore (a subroutine of DFS) to be used as a black box on its own

you should use Explore to check if something is reachable from s. Using DFS requires additional steps that many students forget and end up being penalized for. DFS has many other uses, but Explore is the best algorithm for checking if s can reach certain vertices.

Note:If you simply say, “I run DFS from s and find all vertices reachable by s,” this will likely get you a lack of details penalty, or a “should have used explore” penalty. This is because without additional work, DFS has no output that tells you what vertex was visited from s.

Question 20

DFS: describe, input, output, when to use it, Runtime, access to

Answer 20

DFS is an algorithm for traversing or searching tree or graph data structures. It starts at the root or an arbitrary node of a graph and explores as far as possible along each branch before backtracking

Input: G = (V, E)

Output: ccnum[]

a topological sort on a DAG (Directed Acyclic Graph).

it takes O(1) to access the first or last vertex of the topological sorting.

Graphs that use DFS:
- Unweighted graphs
- Undirected/Directed graphs
- DAGs

Question 21

Explore: describe, input, output, when to use it, Runtime, access to

Answer 21

Explore is used by DFS as a sub-routine.

Very simply, it outlines how to get from one vertex to another along a path in a graph or a tree.

A key point to Explore is that we only move to the next available neighbor only when we have fully explored the current vertex and its adjacencies.

When to use: It is the best algorithm for checking if start vertex v can reach certain vertices in G.

Input:
- G = (V, E)
- Start vertex v in V

Output:
- visited [] (which is set to TRUE for all vertices reachable from v.)

Have access to:
- ccnum array (ccnum[])
- previously visited array (visited[])
- An array of vertices before a given vertex
- Used by Explore and required for DFS.

Graphs that can use Explore
- unweighted graphs
- directed/undirected graphs
- DAGs

Runtime: O(n+m)

Question 22

BFS: describe, input, output, when to use it

Answer 22

algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph) and explores the neighbor nodes at the present depth before moving on to nodes at the next depth level.

Input:
-G = (V, E)
- Start vertex v in V

Output:
dist[]
- For all vertices u reachable from the starting vertex v, dist[u] is the shortest path distance from v to u. If no such path exists, infinity otherwise.

prev[]
-Vertex preceding u in the shortest path from v to reachable vertex u.

Unweighted graphs
Undirected/Directed graphs

Runtime: O(n+m)

Question 23

Dijkstra’s algorithm: describe, input, output, when to use it

Answer 23

Dijkstra’s algorithm is used to find the shortest distance from a source vertex to all other vertices. A path can be recovered by backtracking over all of the pre-labels.

Input:
- G = (V, E)
- Start vertex v in V

Output:
- dist[]
Shortest distance between vertex v and reachable vertex u or infinity otherwise if not reachable.

Have access to:
- prev[]
Vertex preceding u in the shortest path from v to reachable vertex u

Graphs that can use Dijkstra’s:
- Weighted graphs
- Undirected/Directed graphs
- NO negative weights

Runtime: O(m+n log n)
Or if Strongly connected O(m log n)

Question 24

Bellman-Ford: describe, input, output, when to use it

Answer 24

Bellman-Ford is used to derive the shortest path from s to all vertices in V. It does not find a path between all pairs of vertices in V. To do this, we would have to run BF |V| times. Negative weights are allowed

Input:
- G = (V, E)
- Start vertex s

Output:
- The shortest path from vertex s to all other vertices.

We have access to:
- Detect negative weight cycles. We can compare T[n, *] to T[n - 1, *].

• We can only find negative weight cycles that can be reached from starting vertex s

Can use with:
- Weighted graphs
- Undirected/Directed graphs
- CAN HAVE negative weights

Runtime: O(nm)

Question 25

Floyd-Warshall: describe, input, output, when to use it

Answer 25

FW is primarily used to find the shortest path from ALL nodes to all other nodes where negative weights are allowed.

Input:
- G = (V, E)

Output:
- The shortest path from all vertices to all other vertices

We have access to:
- We can detect negative weight cycles by checking the diagonals (T[n, i, i]).

Graphs that can use FW:
- Weighted graphs
- Undirected/Directed graphs
- CAN HAVE negative weights

runtime: O(n^3)

Question 26

SCC algorithm: describe, input, output, when to use it

Answer 26

The SCC algorithm is used to determine the strongly connected components as well as the meta-graph of connected components in a given directed graph

Input:
- G = (V, E)

Output:
- meta-graph (DAG) that contains the connected components

• Topological sorting of the meta-graph
• With a source SCC first and a sink SCC last

We have access to:
- ccnum[] - strongly connected components produced from the 1st DFS run

Graphs that can use SCC:
- directed graphs

Runtime: O(n+m)

Question 27

Kruskal’s Algorithm: describe, input, output, when to use it

Answer 27

Kruskal’s is one of the two algorithms used to find the Minimum Spanning Tree (MST) discussed in class.

Input:
- Connected, Undirected Graph G = (V, E) with edge weights w_e

Output:

• An MST defined by the edges E

Graphs that can use Kruskal’s:

• Connected
• Undirected
• Weighted

Runtime:
- O(m log n)

Question 28

2SAT algorithm: describe, input, output, when to use it

Answer 28

The 2-SAT problem is to determine whether there exists an assignment to variables of a given Boolean formula in 2-CNF (conjunctive normal form) such that the formula evaluates to true. The algorithm for solving 2-SAT uses graph theory by constructing an implication graph and then checking for the existence of a path that satisfies the conditions.

Input:
- A Boolean formula in 2-CNF is represented as a set of clauses where each clause is a disjunction of exactly two literals.

Output:
- A Boolean value indicates whether the given 2-CNF formula is satisfiable. If it is satisfiable, the algorithm may also provide a satisfying assignment of variables

Graphs that can use 2-SAT:
- Directed graphs
The implication graph is inherently directed since each implication (¬x → y) has a direction.

Runtime: O(m + n) - m is the number of clauses in the 2-CNF formula, n is the number of literal or variables.

• This runtime stems from the linear runtime of SCC finding algorithms and the construction of the implication graph

Question 29

Ford-Fulkerson: describe, input, output, when to use it

Answer 29

A greedy algorithm to find max flow on networks. The algorithm continually sends flow along paths from the source (starting node) to the sink (end node), provided there is available capacity on all edges involved. This flow continues until no further augmenting paths with available capacity are detected.

Input:
- G = (V, E)
- Flow capacity c
- Source node s
- Sink node t

Output:
- Max flow

We have access to:
- Can trivially create the final residual network with G
- Max flow of G

We run FF on the flow network to - get the maximum flow.

We use this to construct the residual graph.

Graphs that can use FF:
- Directed graphs with capacity of edges

Runtime:
- O(C * m)
- C is the maximum flow in the network m is the number of edge

Question 30

Edmond’s-Karp: describe, input, output, when to use it

Answer 30

The Edmonds-Karp (EK) algorithm is utilized to determine the maximum flow in a network. This is analogous to the Ford-Fulkerson method but with one distinct difference: the order of search for finding an augmenting path must involve the shortest path with available capacity (BFS for G where all edge weights equal 1).

Input:
- G = (V, E)
- Flow capacity c
- Source node s
- Sink node t

Output:
- Max flow

We have access to:
- Can trivially create the final residual network with G
- Max flow of G

We run EK on the flow network to get the maximum flow.

We use this to construct the residual graph.

Graphs that can use EK:
- Directed graphs with capacity of edges

Runtime:
- O(nm^2)
- n is the number of vertices
- m^2 is the number of edges

Question 31

Why use Edmond’s-Karp over FF?

Answer 31

• Edmonds-Karp uses BFS in the residual graph to find an augmenting path. This guarantees that the path found is always the shortest (in terms of the number of edges). This is crucial because, in Ford-Fulkerson, the use of DFS can lead to long unyieldly path traversals in dense graphs (graphs where the number of edges is close to the maximum possible number of edges), where DFS can get “stuck” exploring a deep path that becomes very inefficient
• The explicit use of BFS for the selection of augmenting paths prevents the possibility of an infinite loop occurring due to constantly decreasing flow augmentation. Therefore, unlike the Ford-Fulkerson algorithm, Edmonds-Karp always terminates.
• Edmonds-Karp algorithm, with its worst-case runtime of O(nm^2), offers an improvement over Ford-Fulkerson because its time complexity is dependent on the number of vertices (n) and edges (m), rather than the maximum flow in the graph (C)