Connected Dominating Set

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

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.

Example

Input:

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).

Graphical representation of the given graph:

Valid Output:

dom(7). dom(8).

The vertices in the dominating set is shown within the rectangle:

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