Artificial Intelligence: Problem Set 1

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.

Problem 1

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.

Problem 2

The second algorithm starts with K = the entire graph and loops through the edges. When it encounters an edge with both ends in K, it non-deterministically chooses an end to delete from K, making sure that K remains a cover.
 
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".