Class Tree  

Description 
Let G=(V,E) be a directed graph. Each edge (u,v) in G is associated with a positive weight w_{u,v}. A subset D of V is a wdominating set of G if, for every vertex v in V, at least one of the following conditions holds: 1. v is in D; 2. sum_{y : (v,y) in E and y in D} w_{v,y} >= w; 3. sum_{z : (z,v) in E and z in D} w_{z,v} >= w. The goal is to find a wdominating set of G of size at most k, where k is another integer specified from the input. Input Format ============ Each input graph is stored in a plain text file. The format of the file is as follows: a. The first n lines define vertices by means of a predicate "vtx" . vtx(1). vtx(2). ... vtx(n). b. The definition of edges follows that of the vertices. The predicate used to define edges is a binary predicate "edge" with edge(i,j) meaning that there is a directed edge going from i to j: edge(1,3). edge(4,2). ... c. The next line defines the size bound of a wdominating set via the predicate "bound(...)." For instance: bound(17). specifies that the wdominating set should have at most 17 vertices. d. The next line contains a single predicate "minweight(w).", which specifies the value of w of the wdominating set. For example, minweight(20). d. The next set of lines contain the definition of edge weights: weight edgewt(1,2) = 8. weight edgewt(2,1) = 9. ... Example vtx(1). vtx(2). vtx(3). vtx(4). edge(1,2). edge(3,2). edge(4,3). edge(4,1). bound(2). minweight(3). weight edgewt(1,2) = 2. weight edgewt(2,1) = 2. weight edgewt(2,3) = 3. weight edgewt(3,2) = 3. weight edgewt(3,4) = 1. weight edgewt(4,3) = 1. weight edgewt(1,4) = 3. weight edgewt(4,1) = 3. Output Requirement ================== The solution must be represented by means of a unary predicate "in". That is atoms of the form "in(u)" must describe all vertices of the wdominating set. For our example input, the following set of ground atoms specifies a valid solution: in(2) in(4) Authors: Lengning Liu and Miroslaw Truszczynski Affiliation: University of Kentucky Email: {lliu1, mirek}@cs.uky.edu 
Encodings 1  4 of 4 
