# Encoding maximal-clique_optimization.gringo

Name maximal-clique_optimization.gringo [Root]    Graph Problems (32) Martin Gebser Martin Gebser and Roland Kaminski 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). 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: 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. For the above example, the only correct output is: clique(1). clique(2). clique(5). Author: Johan Wittocx Affiliation: KU Leuven 2009-03-12 10:42 2009-03-12 16:11 ASP Contest 09 (Maximal Clique) edge/2node/1 clique/1 No ASP Contest 09 (Martin Gebser) uedge(X,Y) :- edge(X,Y), X < Y. uedge(Y,X) :- edge(X,Y), Y < X. { clique(X) : node(X) }. :- clique(X), clique(Y), not uedge(X,Y), X < Y. #maximize { clique(X) : node(X) }. #hide. #show clique(X).