Maximal Clique Problem

Problem Description

This is the problem of finding a maximal clique C in an undirected graph G. That is, for each other clique C' in G, the number of nodes in C should be larger than or equal to the number of nodes in C'.

A directed graph is given as input by facts over the predicates node/1 resp. edge/2, providing the nodes resp. edges. A solution to the problem is a maximal clique in the undirected version of the input graph, i.e. in the symmetric closure of the input graph. A solution is encoded by the predicate clique/1. The set of nodes v, s.t. clique(v) is in the solution, form a clique (not necessarily a maximum clique).

Predicates

• Input: node/1, edge/2

• Output: clique/1

Input format

An instance is a sequence of facts (atoms followed by the dot "." character) with only predicates of the input vocabulary, possibly separated by spaces and line breaks, entirely saved in a text file (instances and files must be in 1-to-1 correspondence). Examples for facts: node(a)., edge(a,b). The terms a and b are positive integers belonging to the vocabulary [1-9][0-9]*.

Output format

The output should consist of a set of facts of the form clique(i). The set of all 'i' that appear in such a fact, should form a maximal clique in the symmetric closure of the input graph.

Example(s)

Input:

node(1). node(2). node(3). node(4). node(5). node(6). 
edge(1,2). edge(1,5). edge(2,3). edge(2,5). edge(3,4). 
edge(4,5). edge(4,6).

For the above example, the following are two correct outputs:

clique(1). clique(2). clique(5).

clique(1). clique(2).

The first is better than the second (in fact, the first is the unique maximum clique).

Additional sample instances: download

Problem Peculiarities

Type: Optimization Competition: System Track

Notes and Updates

Author(s)

• Authors: Guenther Charwat, Martin Kronegger
  • Affiliation: DBAI, Vienna University of Technology, Austria
• Original Author: Johan Wittocx
  • Affiliation: Department of Computer Science, K.U.Leuven, Belgium