Weight-Bounded Dominating Set

Problem description

The Weight-Bounded Dominating Set problem deals with directed graphs G = (V,E), where V is the set of vertices and E the set of edges, such that every edge (i,j) in E is associated with a weight w_(i,j). Furthermore, we consider a certain cardinality k and a minimum weight w. The problem is to find a subset D of V such that |D| ≤ k and, for each vertex v in V, at least one of the following conditions holds:

1. v in D,
2. sum { w_(i,v) : (i,v) in E, i in D } ≥ w, or
3. sum { w_(v,j) : (v,j) in E, j in D } ≥ w.

Input format

An input consists of the following parts:

a. The vertices of the input graph are numbered and given by instances of "vtx" as follows:

vtx(1). vtx(2). ... vtx(n).

b. The edges of the graph are given by instances of "edge" as follows:

edge(1_1,1_2). edge(2_1,2_2). ... edge(m_1,m_2).

An instance edge(i_1,i_2) specifies that there is a directed edge from vertex i_1 to vertex i_2.

c. For each edge(i_1,i_2), there is exactly one instance of "edgewt" providing the edge's (positive) weight w_i:

edgewt(i_1,i_2,w_i).

d. There is exactly one instance of "minweight" specifying the minimum combined weight w of a vertex' predecessors or successors needed to dominate the vertex:

minweight(w).

e. Finally, there is exactly one instance of predicate "bound" specifying the maximum cardinality k of a weight-bounded dominating set D:

bound(k).

For further illustration, compare the instances available at asparagus.

Output format

A solution is represented by means of a unary predicate "in" such that there are at most k instances of "in". The set D of vertices for which "in" holds must be a weight-bounded dominating set for the input graph.

Author: Lengning Liu, Miroslaw Truszczynski, and Martin Gebser
Affiliation: University of Kentucky and University of Potsdam