Trees/Paths/Flows

Question 1

Name the condition under which Dijkstra’s algorithm correctly determines the shortest path between a starting vertex and all other vertices in a graph

Answer 1

Where none of the edges have negative edge weights

Question 2

What algorithm can find the shortest path even despite negative weights?

Answer 2

Algorithms like the Bellman-Ford Algorithm

Question 3

What is a spanning forest?

Answer 3

a spanning forest of a graph is family of subgraphs such that each subgraph is a tree, the trees don’t overlap and every vertex in the spanning forest is contained in a tree

Question 4

What does vertex disjoint mean?

Answer 4

Two trees that are vertex disjoint don’t overlap

Question 5

How many vertices must a spanning tree have to be considered a tree?

What must a graph be to be considered a tree?

Answer 5

1 or more vertices

it must be acyclic (must not contain cycles)

Question 6

What is a spanning tree?

Answer 6

a spanning tree is a spanning forest consisting of a single tree.

Question 7

Does Ford’s algorithm always terminate?

Answer 7

No if the graph contains cycles with edges with negative weights

Question 8

What is a vertex cut?

Answer 8

Partitions a graph into two non-empty sets

Question 9

What is a crossing edge?

Answer 9

The edge that joins two sets, by connecting a vertex in one set to a vertex in another set

Question 10

What is the cut property?

Answer 10

• provides criteria for selecting edges in the MST
• For any vertex cut, the crossing edge between the sets with the most minimum weight is in the MST

Question 11

What are the steps in Prim’s algorithm to find the MST:

Answer 11

1) Start at a random vertex
2) add the edge with the smallest weight to the MST
3) move to the next vertex, do the same
4) if adding the edge with the smallest weight will create a cycle, don’t add it and add the edge with the next smallest weight
5) repeat until we have n-1 edges, for n vertices.

Question 12

Why does Prim’s algorithm work

Answer 12

• We start from a spanning forest where every vertex is its own tree.
• We start at a vertex and keep picking the minimum edge to add to our tree.
• Adding an edge from the spanning forest won’t cause an error, as we only add it if it won’t cause a cycle, so we keep doing this until we have n-1 edges, for n vertices.

Question 13

What are the steps in Kruskal’s algorithm to find the MST:

Answer 13

1) order edges by ascending order of edge weight
2) initialise tree as empty
3) go through list of edges adding the edge to tree as long as it doesn’t cause a cycle
4) return the tree

Question 14

Why does Kruskal’s algorithm work

Answer 14

• Initially our graph holds trivial trees (made of 1 vertex each).
• Whenever we add an edge we connect two trees.
• If we add an edge with the current most minimum weight, until we can’t add anymore edges without creating a cycle, we will have a spanning tree with all the smallest weights.

Question 15

How do we encode a graph problem?

Answer 15

xe for each e ∈ E (decision variable for each edge)

objective is maximise or minimise either weight times edge or just whether to include the edge

constraints: each edge should be 0 or 1, so xe ∈ {0,1}
and flow constraints should hold, how many times each edge should be in set.

Question 16

What is LP relaxation:

Answer 16

Relaxing the constraints of an ILP to change the problem into an LP, so it’s easier to solve

Question 17

What are ILP?

Answer 17

Integer linear programs are where the decision variables must be integers, so only integer solutions are allowed

Question 18

What is the convex hull?

Answer 18

The convex hull conv(S) of a set S ∈ R^n consists of all the convex combinations of points in S

Question 19

When is a convex set integral?

Answer 19

If the convex hull of it’s integer points is the same as the set itself

Question 20

What ILP constraint says the entire graph edges should sum to 1 less than the number of vertices?

Answer 20

Sum of xe for e ∈ E = |V| - 1 where V is the set of all vertices

Question 21

What ILP constraint says the all subsets of vertices should not contain any cycles?

Answer 21

• They should contain vertices in subsets-1 edges for subsets that aren’t empty and aren’t V:

Sum of xe for e ∈ S <= |S|-1 for ∅ ⊂ S ⊂ V

Question 22

How can we prove we have the optimal solution for an ILP:

Answer 22

• By constructing the dual of the ILP encoding and relaxing it, by strong duality, it will show the primal ILP is optimal
• or show that complementary slackness holds for the dual

Question 23

When is a digraph considered simple?

Answer 23

If it has no loops (cycles) or parallel arcs

Question 24

What is the definition of a feasible potential

Question 25

What does a feasible potential provide?

Answer 25

The lower bound for the shortest path costs

Question 26

What constraint says we want incoming edges - outgoing edges = 0 for every vertex except the source and the sink:

Answer 26

Sum of xuv (u,v) ∈ E - Sum of xvw, (v,w) ∈ E = 0 for v ∈ V \ {S, T}

Question 27

For an ILP graph problem what do we assume to get an optimal solution?

Answer 27

That the edges weights are all non-negative

Question 28

What ILP constraint says we want the total of outgoing edges to be 1 for the source?

Answer 28

Sum of xsv = 1, (s,v) ∈ E

Question 29

What ILP constraint says we want the total of incoming edges to be 1 for the target?

Answer 29

Sum of xvt = 1, (v,t) ∈ E

Question 30

What does it mean if there's a negative cost cycle in the graph:

Answer 30

Then the LP is unbounded

Question 31

What condition tells us which edges we need to take for the shortest path?

Answer 31

The feasible potential

Question 32

What is true if u is not a feasible potential after n-1 iterations:

Answer 32

There is a negative cost cycle

Question 33

In the min-flow max cut problem, what must there be for the flow to be improved?

Answer 33

There must be an augmenting path (a path where there is still flow left)

Question 34

What is a residual network?

Answer 34

It shows flow that is leftover along edges (where there is flow remaining that can be pushed along an edge)

Question 35

what condition proves that the dual of the max flow min cut problem gives an optimal solution?

Answer 35

Total unimodularity