Graph Partitioning

Problem description

A  (v,e,k)-graph partition of an undirected weighted graph G=(V,E,W) where V is a set of vertices,  E is a set of edges, and W is a weight function that assigns to each edge in the graph a non-negative integer, is a collection of  k disjoint sets of vertices such that the union of the sets in the collection is V and the following conditions hold:

1. the number of vertices in each set in the partition (i.e., block) is at least 1 and at most v,
2. for every pair of distinct blocks the sum of the weights of the edges between the blocks is at most e, and
3. the subgraph induced by the vertices in each of the blocks 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 always 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 x and y.
3. The weights assigned to each edge "edge(x, y)" are in the following lines by expressions "weight_ wtedge(x,y)=W” where W is a non-negative integer.
4. Next line specifies the number of blocks in a partition, k. The predicate name is “parts”. Partitions are identified by integers that always start at 1 and end at k.
5. Next line provides a non-negative integer bound v on the  number of vertices in each partition. The predicate name is “vtxbound”
6. Finally, the predicate name that provides a non-negative integer bound e on the  total weight of edges between two blocks is “edgebound”

Output format

The programmers must ensure that, in the answer-sets, predicate "partition" is used
to represent the partition found by their solvers. Predicate partition takes two parameters: partition(x,z), which means that the vertex x is in the zth block.

Example

Input:

vtx(1). vtx(2). vtx(3). vtx(4). vtx(5). edge(4,5). edge(2,5). edge(2,3). edge(4,3). edge(4,2). edge(1,5). edge(1,4). edge(5,3). edge(1,2). edge(3,1). weight_wtedge(4,5,1). weight_wtedge(2,5,1). weight_ wtedge(2,3,2). weight_wtedge(4,3,2). weight_wtedge(4,2,1). weight_wtedge(1,5,1). weight_wtedge(1,4,1). weight_wtedge(5,3,2). weight_wtedge(1,2,1). weight_wtedge(3,1,1). parts(1). part(2). part(3). vtxbound(3). edgebound(4).

Graphical representation of the given graph:

partition(1,1).  partition(2,1).  partition(3,1).  partition(4,2).  partition(5,3).

Partitions are represented by rectangles:

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