University of Massachusetts, Amherst CMPSCI 345 hw8-sol

Document Content and Description Below

1. Suppose you are given an n× n checkerboard with some of the squares deleted. You have a large set of dominos, just the right size to cover two squares of the checkerboard. Describe and analyze a... n algorithm to determine whether one tile the board with dominos—each domino must cover exactly two undeleted squares, and each undeleted square must be covered by exactly one domino. Your input is a boolean array Deleted[1.. n,1 .. n], where Deleted[i, j] = True if and only if the square in row i and column j has been deleted. Your output is a single boolean; you do not have to compute the actual placement of dominos. Solution (Reduction to bipartite perfect matching): Given the array Deleted[1 .. n, 1.. n], we first construct a bipartite graph G = (L [ R, E) as follows: • L := (i, j) Deleted[i, j] = False and i + j is even — Intuitively, L is the set of undeleted white squares. • R := (i, j) Deleted[i, j] = False and i + j is odd — Intuitively, R is the set of undeleted black squares. • E := (i, j)(i0, j0) (i, j) 2 L and (i0, j0) 2 R and ji − i0j + jj − j0j = 1 — Intuitively, E is the set of all adjacent pairs of undeleted squares. Every domino must cover one white square and one black square, so if jLj 6= jRj, we can immediately return False. Otherwise, we compute a maximum-cardinality matching in G; if this matching is perfect, we return True, and otherwise, we return False. If we use the matching algorithm presented in class, our algorithm runs in O(V E) = O(n4) time. „ Solution (Reduction to maximum flow): Given the array Deleted[1.. n, 1.. n], we first construct a flow network G = (V, E) as follows: • V := fs, tg [ (i, j) Deleted[i, j] = False . • There are three types of edges: – s
(i, j) for all (i, j) 2 V where i + j is even. – (i, j)
t for all (i, j) 2 V where i + j is odd. – (i, j)
(i0, j0) for all (i, j), (i0, j0) 2 V where i+ j is even and ji−i0j+jj− j0j = 1 – Every edge in G has capacity 1. Intuitively, we have an edge from s to every white square, from every white square to every adjacent black square, and from every adjacent black square to t. Now we compute a maximum (s, t)-flow in G. If the value of this flow is exactly half the number of undeleted squares, return True; otherwise, return False. The maximum flow value is equal to the largest number of non-overlapping dominos we can place on the board, which is trivially at most n2=2. Thus, if we use Ford-Fulkerson to compute the maximum flow, our algorithm runs in O(n2E) = O(n4) time. If we use Orlin’s algorithm to compute the maximum flow, our algorithm still runs in O(V E) = O(n4) time. [Show More]

Last updated: 1 year ago

Preview 1 out of 5 pages