Notes

3.8

(a) We create a directed graph in which a vertex is represented by a triple LaTeX: langle x_0, x_1, x_2 rangle⟨x0,x1,x2⟩. We have that LaTeX: x_0 + x_1 + x_2 = 11x0+x1+x2=11 and LaTeX: x_0 leq c_0 =10, x_1 leq c_1 = 7,text{ and }x_2 leq c_2 = 4x0≤c0=10,x1≤c1=7, and x2≤c2=4. Further, these are all integers.

The initial state of the system is given by the vertex LaTeX: langle 0, 7, 4rangle⟨0,7,4⟩.

We denote valid pouring operations using edges. Note that a pouring operation is valid if two vertices differ in exactly two coordinates, and if the differing coordinates are LaTeX: ii and LaTeX: jj, we must have that LaTeX: x_i = 0 text{ or } x_j = 0 text{ or } y_i = c_i text{ or } y_j = c_jxi=0 or xj=0 or yi=ci or yj=cj.

We now want to answer the question if there is a path from LaTeX: langle 0, 7, 4rangle⟨0,7,4⟩ to a vertex of the form LaTeX: langle *, 2, *rangle⟨∗,2,∗⟩ or LaTeX: langle *, *, 2rangle⟨∗,∗,2⟩.

(b) We can invoke the explore routine from LaTeX: langle 0, 7, 4rangle⟨0,7,4⟩ and incrementally construct the graph edges. We are done if we reach a vertex of the desired form, or when the explore routine finishes.

3.14

When we remove a source vertex, we reduce in-degree of the vertices it is connected to. We can use a list to keep track of newly created source vertices once the older vertices are deleted. The approach finishes in time linear in the number of DAG edges.

3.16

We compute the longest path in the DAG. The algorithm uses dynamic programming. Linearization helps.

3.22

Given a directed graph, we want to determine if there exists a vertex LaTeX: ss from which all other vertices are reachable. So if we invoke explore from LaTeX: ss, all vertices in the graph must be visited. Notice that if we do an SCC decomposition of the graph, there must be at least one source SCC in the SCC metagraph. The vertex LaTeX: ss (if it exists) must belong to a source SCC, and further, there must be only one source SCC. We can invoke explore from one of the vertices in the source SCC to check if all other vertices are visited. If they are not visited, then it means the graph does not have such a vertex LaTeX: ss.

3.23

Do a topological sort and get the locations of s and t in the topological sort. Notice that any paths from s to t could only pass through vertices that lie between s and t in the topological sort, and we can ignore all other vertices. We can start from s and count the number of paths to each intermediate vertex. It is possible to write down a recurrence for the path counts.

3.24

Do a topological sort and check if every pair of consecutive vertices are connected.

3.25

(a) Do a topological sort and visit vertices in reversed order, propagating cost values.

(b) The cost of all vertices in an SCC will be the same, because all pairs of vertices in an SCC are connected. So perform an SCC decomposition, construct the metagraph and use the algorithm for part (a) on this graph.