welcome:
location: MaximalClique

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

## Problem Peculiarities

Type: Optimization Competition: System Track