=  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: [[https://www.mat.unical.it/aspcomp2013/files/samples/maximal_clique-sample.zip|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