3. Suppose you are given an n x n checkerboard with some of the squares deleted....

  

Transcribed Image Text:

3. Suppose you are given an n x n checkerboard with some of the squares deleted. You have a large set of dominos, each just the right size to cover two neighboring squares of the checkerboard. Tiling the board with dominos means placing dominos so each domino covers exactly two squares and each undeleted square is covered by exactly one domino. A checkerboard tiled with dominos. We will design an algorithm to determine whether one can tile a board with dominos by reducing to maximum matching in a bipartite graph. (a) A bipartite graph G has two sets of vertices U and W. What should we use for each of the sets U and W? [Hint: Our goal is to cover all the undeleted squares of the checkerboard. You may want to check what the squares of a checkerboard look like.] (b) What should we use for our set of edges? [Hint: A matching is a subset of edges that is incident to each vertex at most once.] (c) What should the size of the maximum matching be if we can tile the given checker- board? (d) In terms of n, how long does it take to determine if we can tile the checkerboard using this reduction? 3. Suppose you are given an n x n checkerboard with some of the squares deleted. You have a large set of dominos, each just the right size to cover two neighboring squares of the checkerboard. Tiling the board with dominos means placing dominos so each domino covers exactly two squares and each undeleted square is covered by exactly one domino. A checkerboard tiled with dominos. We will design an algorithm to determine whether one can tile a board with dominos by reducing to maximum matching in a bipartite graph. (a) A bipartite graph G has two sets of vertices U and W. What should we use for each of the sets U and W? [Hint: Our goal is to cover all the undeleted squares of the checkerboard. You may want to check what the squares of a checkerboard look like.] (b) What should we use for our set of edges? [Hint: A matching is a subset of edges that is incident to each vertex at most once.] (c) What should the size of the maximum matching be if we can tile the given checker- board? (d) In terms of n, how long does it take to determine if we can tile the checkerboard using this reduction?