Problem Set 3

Assigned: March 2.
Due: March 23.

Problem 1

The VERTEX COVER problem is defined as follows. You are given: 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.

Answer:

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.

Answer:

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:

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