welcome: please sign in
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).


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.



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


ASP Competition 2013: MaximalClique (last edited 2012-11-20 22:20:00 by PatrikSchneider)