Instance Class WeightBoundedDominatingSetSuite

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 w-dominating 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 w-dominating 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 w-dominating set via the
predicate "bound(...)." For instance:
bound(17).
specifies that the w-dominating 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 w-dominating 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
w-dominating 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
Submitter Martin Gebser
Compatible Encodings
Output Predicates
  • bound/1
  • edge/2
  • edgewt/3
  • minweight/1
  • vtx/1
Instances
1 - 20 of 30