|
Size: 2006
Comment: Maximal Clique added
|
← Revision 6 as of 2012-11-20 22:20:00 ⇥
Size: 2293
Comment: Link to sample instances added
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 3: | Line 3: |
| <<TableOfContents>> | |
| Line 7: | Line 6: |
| 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'. | 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'. |
| Line 9: | Line 8: |
| 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). | 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). |
| Line 19: | Line 18: |
| 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)}}}. | 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]*. |
| Line 28: | Line 27: |
| 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).}}} | 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). }}} |
| Line 31: | Line 35: |
| * {{{clique(1). clique(2). clique(5).}}} * {{{clique(1). clique(2).}}} |
{{{ clique(1). clique(2). clique(5). }}} {{{ clique(1). clique(2). }}} |
| Line 35: | Line 43: |
Additional sample instances: [[https://www.mat.unical.it/aspcomp2013/files/samples/maximal_clique-sample.zip|download]] == Problem Peculiarities == '''Type''': Optimization '''Competition''': System Track |
|
| Line 41: | Line 56: |
| * Affiliation: Vienna University of Technology, Austria | * Affiliation: DBAI, Vienna University of Technology, Austria |
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: 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