## Problem Set 3

Assigned: March 2.
Due: March 23.

### Problem 1

The VERTEX COVER problem is defined as follows. You are given:
• An undirected graph.
• A number K.
The problem is to find a subset S of the vertices of size at most K such that every edge in the graph has at least one end in S.

For instance, in graph I, { A,C,E } is a vertex cover of size 3. In graph II, { T } is a vertex cover of size 1.

An instance of the vertex cover problem can be translated into a Boolean satisfiability problem by using atoms of the form P-I, meaning that vertex P is the Ith element of set S (the order of elements in the set is arbitrary). For instance to solve the problem of finding a vertex cover for graph I, one would use the atoms A-1, A-2, A-3, B-1, B-2 ... F-1, F-2, F-3. One way to indicate the above solution to the problem would be the valuation A-2 => TRUE, C-1 => TRUE, E-3 => TRUE, and the remaining atoms are false.

Describe the propositional constraints that would be needed to express the vertex cover problem, and for each category of constraints give two examples from the encoding of Graph I.

• For each number K and for each pair of vertices U != V, assert that U and V are not both the Kth element. Examples: ~(A-1 ^ V-1). ~(C-2 ^ F-2).
• For each pair of numbers J != K and vertex U, assert that U is not both the Jth and Kth element. Examples: ~(A-1 ^ A-2). ~(D-2 ^ D-3). (This is actually optional; if it is omitted, the satisfaction algorithm may find covers with repeated elements.)
• For each edge U-V, assert that either U-I or V-J holds for some value of I and J. Examples:
A-1 V A-2 V A-3 V B-1 V B-2 V B-3.
D-1 V D-2 V D-3 V E-1 V E-2 V E-3.

### Problem 2

The EDGE COVER problem is the problem of finding a set S of K edges in a given undirected graph G such that all the vertices of G are in some edge in S. For instance {A-B, C-D, E-F} is an edge cover of size 3 for graph I. The only edge cover for graph II is the entire set of edges.

Describe how any instance of the edge cover problem can be encoded in the propositional calculus. As in problem 1, specify what the atoms are; describe the constraints; and illustrate each category of constraints with two examples from graph I.

Atoms: For each edge U-V and each number I between 1 and K, there is an atom U-V-I which asserts that U-V is the Ith element of S.

Propositions:

• For each pair of edges U-V, W-X and each number I, assert that U-V and W-X are not both the Ith element. E.g. ~(A-B-1 ^ B-C-1). ~(A-C-3 ^ E-F^3).
• For each edge U-V and pairs of numbers I,J, assert that U-V is not both the Ith and Jth element. E.g. ~(A-B-1 ^ A-B-2). ~(D-E-1 ^ D-E-2). (Again this is optional, as in problem 1).
• For each vertex U, assert that that one of the edges ending at U is in the set S at some index I. E.g.
For vertex A: A-B-1 V A-B-2 V A-B-3 V A-C-1 V A-C-2 V A-C-3 V A-F-1 V A-F-2 V A-F-3
For vertex D: C-D-1 V C-D-2 V C-D-3 V D-E-1 V D-E-2 V D-E-3
(Incidentally, edge cover has a polynomial time algorithm, so converting to propositional form and using Davis-Putnam is probably not a winning strategy.)

### Problem 3

Let O be a universe of containing stores and people. Let L be the first-order language over O with the following non-logical symbols:
W(P,S) -- Person P works for store S.
C(P,S) -- Person P is a customer at store S.
B(P1,P2) -- Person P1 is a boss of person P2.
M(P1,P2) --- Person P1 is married to P2.
D(P,S) --- Person P is entitled to a discount at store S.
A, T, K, G --- Andy, Tara, K-Mart, Gristedes.
Express the following sentences in L.
• A. Andy works at both K-Mart and Gristedes.