## 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.

```

```

### 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.

### 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.
• B. All of Tara's subordinates are married.
• C. Any employee of a store and their spouse are entitled a discount at that store. (Note: employees get their discount whether or not they are married).
• D. Tara is Andy's boss.
• E. There is no married couple both of whom work at Gristedes.
• F. There exists someone who does not work at Gristedes but is nonetheless entitled to a discount at Gristedes.
• G. There exists a store that only employs married couples (that is, the store employs a person P only if P is married and P's spouse is likewise an employee.)