Class Tree
Description Problem description

A connected dominating set in an undirected graph G=(V,E), where V is a set of vertices, and E is a set of edges, is a subset D of vertices in the graph such that the following two conditions hold:

1. for every vertex v in V: either v is in D, or there is a vertex u in D such that uv is an edge of G
2. the subgraph induced by the vertices in D is connected

Goal: Given a graph and an integer k, find a connected dominating set with at most k vertices.

Input format

Input graphs are stored in plain text files, one file for each graph. The format of the file is as follows:

1. The file starts with lines that define vertices. Vertices are defined using predicate name "vtx". Vertices are represented as integers that start from 1 and end at n, where n is the number of the vertices.
2. The definition of edges follows. The predicate name used to define edges is "edge". Predicate edge has two parameters. Intuitively, edge(x, y) means there is an undirected edge between vertex x and vertex y (we assume no loops).
3. The predicate name that provides the bound k on the number of vertices in the dominating set is “bound”.
4. Every line ends with "."

Output format

The programmers must ensure that, in the answer-sets, predicate "dom" is used to represent the dominating set found by their solvers. Predicate dom takes one parameter: dom(x), which means that the vertex x is in the connected dominating set of size at most the specified bound.



vtx(1). vtx(2). vtx(3). vtx(4). vtx(5). vtx(6). vtx(7). vtx(8). edge(8,5). edge(7,4). edge(8,7). edge(7,5). edge(6,7). edge(8,1). edge(3,4). edge(6,1). edge(6,2). edge(3,5). edge(1,5). edge(5,4). edge(3,7). edge(5,2). edge(2,8). edge(3,1). edge(7,1). edge(6,4). edge(4,2). edge(8,4). bound(3).

Valid Output:

dom(7). dom(8).

Authors: Gayathri Namasivayam and Miroslaw Truszczynski
Affiliation: University of Kentucky
1 - 1 of 1