Encoding maximal-clique_optimization.gringo

Name maximal-clique_optimization.gringo
Class Tree
Submitter Martin Gebser
Author Martin Gebser and Roland Kaminski
Description 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:


The edges of the graph are given by facts of the form:


The following is an example 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).

Output format

The output should consist of a set of facts of the form:


The set of all 'i' that appear in such a fact, should form a maximal clique in the symmetric closure of the input graph.

For the above example, the only correct output is:

clique(1). clique(2). clique(5).

Author: Johan Wittocx
Affiliation: KU Leuven
Created 2009-03-12 10:42
Modified 2009-03-12 16:11
Language Features
Compatible Instance Classes
Input Predicates
  • edge/2
  • node/1
Output Predicates
  • clique/1
Encoding Parameter
    Standalone Help No
    • ASP Contest 09 (Martin Gebser)