# 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