CS 473 Homework 8 Solutions Fall 2016
1. Suppose we are given an n × n grid, some of whose cells are marked; the grid is represented by an array
M[1..n, 1..n] of booleans, where M[i, j] = True if and only if cell (i, j) is marked. A monotone path through
the grid starts at the top-left cell, moves only right or down at each step, and ends at the bottom-right cell.
Our goal is to cover the marked cells with as few monotone paths as possible.
É Not to submit: Describe an algorithm to find a monotone path that covers the largest number of
marked cells.
Solution: We construct a graph G.
• G has two vertices ui,j and vi,j for each pair of array indices i and j.
• Each vertex ui,j has an edge to its partner vi,j. Each partner edge has length 1 if
M[i, j] = TRUE and length 0 otherwise.
• Each vertex vi,j has edges to its right neighbor ui+1,j and its downward neighbor ui,j+1
(if they exist). Neighbor edges have length 0.
Each monotone path through the grid is represented by a directed path in G. Conversely,
every directed path in G represents a monotone path through the grid. Thus, if we can cover k
marked cells with a monotone path, then there is a path of length k in the graph. Conversely,
if the graph has a path of length k, that path corresponds to a monotone path that must cover
k marked cells. So we can solve find the monotone path that covers the largest number of
marked cells in the grid by finding the longest path in G from u1,1.
The graph G has O(n2) vertices and edges, and we can construct it in O(n2) time. Since G
is a DAG, finding the longest path can be done in O(jVj + jEj) = O(n2) time using Dynamic
Programming. „
É Not to submit: There is a natural greedy heuristic to find a small cover by monotone paths: If there
are any marked cells, find a monotone path Π that covers the largest number of marked cells, unmark
any marked cells covered by Π, and recurse. Show that this algorithm does not always compute an
optimal solution.
Solution: Here is a 6 × 6 counterexample:
The greedy strategy is not optimal.
The middle figure shows a greedy path; in fact any greedy monotone path covers the same
four marked cells. If we start with a greedy path, we need two more monotone paths to cover
the other two marked cells. The right figure shows that the marked cells can all be covered
with just two monotone paths. „
É Describe and analyze an efficient algorithm to compute the smallest set of monotone paths that
covers every marked cell.
Solution (Reduction to flow with lower bounds): Consider the following decision problem: Can the marked cells be covered using at most k monotone paths? If we can solve the
decision problem efficiently, then we can find the minimum number of paths efficiently by
performing binary search over the possible values of k.
We construct a directed flow network G, with both capacities and lower bounds on the
edges,