=  Maximal Clique Problem =

<<TableOfContents>>

== 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'. 

As input, a directed graph is given, encoded by facts over the predicates node/1 and edge/2, providing respectively the nodes and the 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 such that {{{clique(v)}}} holds should form a maximal clique (possibly one of maximum cardinality).

== Predicates ==

 * '''Input''': {{{node/1, edge/2}}}

 * '''Output''': {{{clique/1}}}

== Input format ==

As input, a directed graph is given. A solution is the largest clique in the symmetric closure of this input graph. The nodes of the input graph are given by facts of the form {{{node(i)}}}. The edges of the graph are given by facts of the form {{{edge(i,j)}}}.

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

== Notes and Updates ==

 * Specification: updated "Output format" section on date 01/02/2011;

== Author(s) ==
 * Author: Johan Wittocx
   * Affiliation: Department of Computer Science, K.U.Leuven, Belgium