Assigned: Jan. 22

Due: Feb. 5

Let G = < V,E > be a directed graph, where V is the set of vertices
and E is the set of edges. Let K be a subset of V. K is called
an *independent set* if no two vertices in K are connected by
an edge in E. A vertex u is said to *cover* vertex v if
either u=v or the edge u -> v is in E. The set K is called a
* cover * for G if every vertex in V has a cover in K.
The set K is called a *kernel* for G if K is both an
independent set and a cover.
For example, in the diagram below, {A,C} is a kernel for graph 1. {B,D}
is also a kernel for graph 1.
{F,H} is the only kernel for graph 2. There is no kernel for graph 3.

In this problem set, we consider two non-deterministic algorithms for finding the kernel of a given graph.

The first algorithm starts with K = the empty set, and loops through the vertices. When it reaches an uncovered vertex W, it adds a cover for W to K, making sure that K remains an independent set.

function kernel1(in V : set of vertices; E : set of arcs) return set of vertices. begin K := emptyset; for W in V do begin choose a vertex U in V such that covers(U,W,E); if blocked(U,K,E) then fail else add U to K end return K end; function covers(in U,W : vertex; E : set of arcs) return boolean; return [(U=W) or (U -> W is in E)] end covers /* blocked(U,K,E) returns true if it is not allowed to add U to K */ function blocked(U : vertex; K : set of vertices; E : set of arcs) return boolean; return [there exists a vertex Q in K such that Q -> U is in E or U -> Q is in E] end blocked.

- A. Suppose that the search is implemented using a depth-first search,
and that vertices are enumerated in alphabetical order. Show the portion
of the search tree generated by the DFS up to the point where it finds
its first solution.
- B. Characterize the state space explored in this algorithm. What is a state? What is an operation? What is the start space? What is a goal state?
- C. What is the depth D of this state space? What is the
maximal branching factor B? Give an upper bound on the size
of the state space that is significantly smaller than B
^{D}.

function kernel2(in V : set of vertices; E : set of arcs) return set of vertices. begin K := V; for each edge < U,W > in E do if both U and W are in K then begin either Q := U or Q := W; delete Q from K; if not k-covers(K,V,E) then fail end end kernel2. function k-covers(in K,V : set of vertices; E : set of edges) return boolean; return [ for every U in V there exists W in K such that covers(W,U,E) ] end k-covers.

Note: the operator "either" above is a non-deterministic choice between the two options. It works in the same way as "choose".

- A. Suppose that the search is implemented using a depth-first search; that the first branch of the "either" statement is explored before the second; and that edges are enumerated in lexicographic order: B -> A, B -> C, C -> D, D -> E, E -> A, E -> B. Show the portion of the search tree generated by the DFS up to the point where it finds its first solution.
- B. Characterize the state space explored in this algorithm. What is a state? What is an operation? What is the start space? What is a goal state?
- C. What is the depth D of this state space? What is the maximal branching factor B?