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