Goto Chapter: Top 1 2 3 4 5 6 7 8 9 A Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

8 Finding cliques and independent sets
 8.1 Finding cliques
 8.2 Finding independent sets

8 Finding cliques and independent sets

In Digraphs, a clique of a digraph is a set of mutually adjacent vertices of the digraph, and an independent set is a set of mutually non-adjacent vertices of the digraph. A maximal clique is a clique which is not properly contained in another clique, and a maximal independent set is an independent set which is not properly contained in another independent set. Using this definition in Digraphs, cliques and independent sets are both permitted, but not required, to contain vertices at which there is a loop. Another name for a clique is a complete subgraph.

Digraphs provides extensive functionality for computing cliques and independent sets of a digraph, whether maximal or not. The fundamental algorithm used in most of the methods in Digraphs to calculate cliques and independent sets is a version of the Bron-Kerbosch algorithm. Calculating the cliques and independent sets of a digraph is a well-known and hard problem, and searching for cliques or independent sets in a digraph can be very length, even for a digraph with a small number of vertices. Digraphs uses several strategies to increase the performance of these calculations.

From the definition of cliques and independent sets, it follows that the presence of loops and multiple edges in a digraph is irrelevant to the existence of cliques and independent sets in the digraph. See DigraphHasLoops (6.1-1) and IsMultiDigraph (6.1-8) for more information about these properties. Therefore given a digraph digraph, the cliques and independent sets of digraph are equal to the cliques and independent sets of the digraph:

See DigraphRemoveLoops (3.3-22) and DigraphRemoveAllMultipleEdges (3.3-23) for more information about these attributes. Furthermore, the cliques of this digraph are equal to the cliques of the digraph formed by removing any edge [u,v] for which the corresponding reverse edge [v,u] is not present. Therefore, overall, the cliques of digraph are equal to the cliques of the symmetric digraph:

See MaximalSymmetricSubdigraphWithoutLoops (3.3-4) for more information about this attribute. The AutomorphismGroup (7.2-1) of this symmetric digraph contains the automorphism group of digraph as a subgroup. By performing the search for maximal cliques with the help of this larger automorphism group to reduce the search space, the computation time may be reduced. The functions and attributes which return representatives of cliques of digraph will return orbit representatives of cliques under the action of the automorphism group of the maximal symmetric subdigraph without loops on sets of vertices.

The independent sets of a digraph are equal to the independent sets of the DigraphSymmetricClosure (3.3-9). Therefore, overall, the independent sets of digraph are equal to the independent sets of the symmetric digraph:

Again, the automorphism group of this symmetric digraph contains the automorphism group of digraph. Since a search for independent sets is equal to a search for cliques in the DigraphDual (3.3-8), the methods used in Digraphs usually transform a search for independent sets into a search for cliques, as described above. The functions and attributes which return representatives of independent sets of digraph will return orbit representatives of independent sets under the action of the automorphism group of the symmetric closure of the digraph formed by removing loops and multiple edges.

Please note that in Digraphs, cliques and indepedent sets are not required to be maximal. Some authors use the word clique to mean maximal clique, and some authors use the phrase independent set to mean maximal independent set, but please note that Digraphs does not use this definition.

8.1 Finding cliques

8.1-1 IsClique
‣ IsClique( digraph, l )( operation )
‣ IsMaximalClique( digraph, l )( operation )

Returns: true or false.

If digraph is a digraph and l is a duplicate-free list of vertices of digraph, then IsClique(digraph,l) returns true if l is a clique of digraph and false if it is not. Similarly, IsMaximalClique(digraph,l) returns true if l is a maximal clique of digraph and false if it is not.

A clique of a digraph is a set of mutually adjacent vertices of the digraph. A maximal clique is a clique which is not properly contained in another clique. A clique is permitted, but not required, to contain vertices at which there is a loop.

gap> gr := CompleteDigraph(4);;
gap> IsClique(gr, [1, 3, 2]);
true
gap> IsMaximalClique(gr, [1, 3, 2]);
false
gap> IsMaximalClique(gr, DigraphVertices(gr));
true
gap> gr := Digraph([[1, 2, 4, 4], [1, 3, 4], [2, 1], [1, 2]]);
<multidigraph with 4 vertices, 11 edges>
gap> IsClique(gr, [2, 3, 4]);
false
gap> IsMaximalClique(gr, [1, 2, 4]);
true

8.1-2 CliquesFinder
‣ CliquesFinder( digraph, hook, user_param, limit, include, exclude, max, size, reps )( function )

Returns: The argument user_param.

This function finds cliques of the digraph digraph subject to the conditions imposed by the other arguments as described below. Note that a clique is represented by a list of the vertices which it contains.

Let G denote the automorphism group of the maximal symmetric subdigraph of digraph without loops (see AutomorphismGroup (7.2-1) and MaximalSymmetricSubdigraphWithoutLoops (3.3-4)).

hook

This argument should be a function or fail.

If hook is a function, then it should have two arguments user_param (see below) and a clique c. The function hook(user_param, c) is called every time a new clique c is found by CliquesFinder.

If hook is fail, then a default function is used which simply adds every new clique found by CliquesFinder to user_param, which must be a list in this case.

user_param

If hook is a function, then user_param can be any GAP object. The object user_param is used as the first argument for the function hook. For example, user_param might be a list, and hook(user_param, c) might add the size of the clique c to the list user_param.

If the value of hook is fail, then the value of user_param must be a list.

limit

This argument should be a positive integer or infinity. CliquesFinder will return after it has found limit cliques or the search is complete.

include and exclude

These arguments should each be a (possibly empty) duplicate-free list of vertices of digraph (i.e. positive integers less than the number of vertices of digraph).

CliquesFinder will only look for cliques containing all of the vertices in include and containing none of the vertices in exclude.

Note that the search may be much more efficient if each of these lists is invariant under the action of G on sets of vertices.

max

This argument should be true or false. If max is true then CliquesFinder will only search for maximal cliques. If max is false then non-maximal cliques may be found.

size

This argument should be fail or a positive integer. If size is a positive integer then CliquesFinder will only search for cliques which contain precisely size vertices. If size is fail then cliques of any size may be found.

reps

This argument should be true or false.

If reps is true then the arguments include and exclude are each required to be invariant under the action of G on sets of vertices. In this case, CliquesFinder will find representatives of the orbits of the desired cliques under the action of G, although representatives may be returned which are in the same orbit. If reps is false then CliquesFinder will not take this into consideration.

For a digraph such that G is non-trivial, the search for clique representatives can be much more efficient than the search for all cliques.

This function uses a version of the Bron-Kerbosch algorithm.

gap> gr := CompleteDigraph(5);
<digraph with 5 vertices, 20 edges>
gap> user_param := [];;
gap> f := function(a, b) # Calculate size of clique
>   AddSet(user_param, Size(b));
> end;;
gap> CliquesFinder(gr, f, user_param, infinity, [], [], false, fail, 
>                  true);
[ 1, 2, 3, 4, 5 ]
gap> CliquesFinder(gr, fail, [], 5, [2, 4], [3], false, fail, false);
[ [ 2, 4 ], [ 1, 2, 4 ], [ 2, 4, 5 ], [ 1, 2, 4, 5 ] ]
gap> CliquesFinder(gr, fail, [], 2, [2, 4], [3], false, fail, false);
[ [ 2, 4 ], [ 1, 2, 4 ] ]
gap> CliquesFinder(gr, fail, [], infinity, [], [], true, 5, false);
[ [ 1, 2, 3, 4, 5 ] ]
gap> CliquesFinder(gr, fail, [], infinity, [1, 3], [], false, 3, false);
[ [ 1, 2, 3 ], [ 1, 3, 4 ], [ 1, 3, 5 ] ]
gap> CliquesFinder(gr, fail, [], infinity, [1, 3], [], true, 3, false);
[  ]

8.1-3 DigraphClique
‣ DigraphClique( digraph[, include[, exclude[, size]]] )( function )
‣ DigraphMaximalClique( digraph[, include[, exclude[, size]]] )( function )

Returns: A list of positive integers, or fail.

If digraph is a digraph, then these functions returns a clique of digraph if one exists which satisfies the arguments, else it returns fail. A clique is defined by the set of vertices which it contains; see IsClique (8.1-1) and IsMaximalClique (8.1-1).

The optional arguments include and exclude must each be a (possibly empty) duplicate-free list of vertices of digraph, and the optional argument size must be a positive integer. By default, include and exclude are empty. These functions will search for a clique of digraph which includes the vertices of include and which does not include any vertices in exclude; if the argument size is supplied, then additionally the clique will be required to contain precisely size vertices.

If include is not a clique, then these functions return fail. Otherwise, the functions behave in the following way, depending on the number of arguments:

One or two arguments

If one or two arguments are supplied, then DigraphClique and DigraphMaximalClique greedily enlarge the clique include until it can not continue. The result is guaranteed to be a maximal clique. This may or may not return an answer more quickly than using DigraphMaximalCliques (8.1-4). with a limit of 1.

Three arguments

If three arguments are supplied, then DigraphClique greedily enlarges the clique include until it can not continue, although this clique may not be maximal.

Given three arguments, DigraphMaximalClique returns the maximal clique returned by DigraphMaximalCliques(digraph, include, exclude, 1) if one exists, else fail.

Four arguments

If four arguments are supplied, then DigraphClique returns the clique returned by DigraphCliques(digraph, include, exclude, 1, size) if one exists, else fail. This clique may not be maximal.

Given four arguments, DigraphMaximalClique returns the maximal clique returned by DigraphMaximalCliques(digraph, include, exclude, 1, size) if one exists, else fail.

gap> gr := Digraph([[2, 3, 4], [1, 3], [1, 2], [1, 5], []]);
<digraph with 5 vertices, 9 edges>
gap> IsSymmetricDigraph(gr);
false
gap> DigraphClique(gr);
[ 5 ]
gap> DigraphMaximalClique(gr);
[ 5 ]
gap> DigraphClique(gr, [1, 2]);
[ 1, 2, 3 ]
gap> DigraphMaximalClique(gr, [1, 3]);
[ 1, 3, 2 ]
gap> DigraphClique(gr, [1], [2]);
[ 1, 4 ]
gap> DigraphMaximalClique(gr, [1], [3, 4]);
fail
gap> DigraphClique(gr, [1, 5]);
fail
gap> DigraphClique(gr, [], [], 2);
[ 1, 2 ]

8.1-4 DigraphMaximalCliques
‣ DigraphMaximalCliques( digraph[, include[, exclude[, limit[, size]]]] )( function )
‣ DigraphMaximalCliquesReps( digraph[, include[, exclude[, limit[, size]]]] )( function )
‣ DigraphCliques( digraph[, include[, exclude[, limit[, size]]]] )( function )
‣ DigraphCliquesReps( digraph[, include[, exclude[, limit[, size]]]] )( function )
‣ DigraphMaximalCliquesAttr( digraph )( attribute )
‣ DigraphMaximalCliquesRepsAttr( digraph )( attribute )

Returns: A list of lists of positive integers.

If digraph is digraph, then these functions and attributes use CliquesFinder (8.1-2) to return cliques of digraph. A clique is defined by the set of vertices which it contains; see IsClique (8.1-1) and IsMaximalClique (8.1-1).

The optional arguments include and exclude must each be a (possibly empty) list of vertices of digraph, the optional argument limit must be either a positive integer or infinity, and the optional argument size must be a positive integer. If not specified, then include and exclude are empty lists, and limit is infinity.

The functions will return as many suitable cliques as possible, up to the number limit. These functions will find cliques which contain all of the vertices of include and which do not contain any of the vertices of exclude. The argument size restricts the search to those cliques which contain precisely size vertices. If the function or attribute has Maximal in its name, then only maximal cliques will be returned; otherwise non-maximal cliques may be returned.

Let G denote the automorphism group of maximal symmetric subdigraph of digraph without loops (see AutomorphismGroup (7.2-1) and MaximalSymmetricSubdigraphWithoutLoops (3.3-4)).

Distinct cliques

DigraphMaximalCliques and DigraphCliques each return a duplicate-free list of at most limit cliques of digraph which satisfy the arguments.

The computation may be significantly faster if include and exclude are invariant under the action of G on sets of vertices.

Orbit representatives of cliques

To use DigraphMaximalCliquesReps or DigraphCliquesReps, the arguments include and exclude must each be invariant under the action of G on sets of vertices.

If this is the case, then DigraphMaximalCliquesReps and DigraphCliquesReps each return a duplicate-free list of at most limit orbits representatives (under the action of G on sets vertices) of cliques of digraph which satisfy the arguments.

The representatives are not guaranteed to be in distinct orbits. However, if lim is not specified, or fewer than lim results are returned, then there will be at least one representative from each orbit of maximal cliques.

gap> gr := Digraph([
> [2, 3], [1, 3], [1, 2, 4], [3, 5, 6], [4, 6], [4, 5]]);
<digraph with 6 vertices, 14 edges>
gap> IsSymmetricDigraph(gr);
true
gap> G := AutomorphismGroup(gr);
Group([ (5,6), (1,2), (1,5)(2,6)(3,4) ])
gap> DigraphMaximalCliques(gr);
[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 3, 4 ] ]
gap> DigraphMaximalCliquesReps(gr);
[ [ 1, 2, 3 ], [ 3, 4 ] ]
gap> Orbit(G, [1, 2, 3], OnSets);
[ [ 1, 2, 3 ], [ 4, 5, 6 ] ]
gap> Orbit(G, [3, 4], OnSets);
[ [ 3, 4 ] ]
gap> DigraphMaximalCliquesReps(gr, [3, 4], [], 1);
[ [ 3, 4 ] ]
gap> DigraphMaximalCliques(gr, [1, 2], [5, 6], 1, 2);
[  ]
gap> DigraphCliques(gr, [1], [5, 6], infinity, 2);
[ [ 1, 2 ], [ 1, 3 ] ]

8.1-5 CliqueNumber
‣ CliqueNumber( digraph )( attribute )

Returns: A non-negative integer.

If digraph is a digraph, then CliqueNumber(digraph) returns the largest integer n such that digraph contains a clique with n vertices as an induced subdigraph.

A clique of a digraph is a set of mutually adjacent vertices of the digraph. Loops and multiple edges are ignored for the purpose of determining the clique number of a digraph.

gap> gr := CompleteDigraph(4);;
gap> CliqueNumber(gr); 
4
gap> gr := Digraph([[1, 2, 4, 4], [1, 3, 4], [2, 1], [1, 2]]);
<multidigraph with 4 vertices, 11 edges>
gap> CliqueNumber(gr); 
3

8.2 Finding independent sets

8.2-1 IsIndependentSet
‣ IsIndependentSet( digraph, l )( operation )
‣ IsMaximalIndependentSet( digraph, l )( operation )

Returns: true or false.

If digraph is a digraph and l is a duplicate-free list of vertices of digraph, then IsIndependentSet(digraph,l) returns true if l is an independent set of digraph and false if it is not. Similarly, IsMaximalIndependentSet(digraph,l) returns true if l is a maximal independent set of digraph and false if it is not.

An independent set of a digraph is a set of mutually non-adjacent vertices of the digraph. A maximal independent set is an independent set which is not properly contained in another independent set. An independent set is permitted, but not required, to contain vertices at which there is a loop.

gap> gr := CycleDigraph(4);;
gap> IsIndependentSet(gr, [1]);
true
gap> IsMaximalIndependentSet(gr, [1]);
false
gap> IsIndependentSet(gr, [1, 4, 3]);
false
gap> IsIndependentSet(gr, [2, 4]);
true
gap> IsMaximalIndependentSet(gr, [2, 4]);
true

8.2-2 DigraphIndependentSet
‣ DigraphIndependentSet( digraph[, include[, exclude[, size]]] )( function )
‣ DigraphMaximalIndependentSet( digraph[, include[, exclude[, size]]] )( function )

Returns: A lists of positive integers, or fail.

If digraph is a digraph, then these functions returns a independent set of digraph if one exists which satisfies the arguments, else it returns fail. A independent set is defined by the set of vertices which it contains; see IsIndependentSet (8.2-1) and IsMaximalIndependentSet (8.2-1).

The optional arguments include and exclude must each be a (possibly empty) duplicate-free list of vertices of digraph, and the optional argument size must be a positive integer. By default, include and exclude are empty. These functions will search for a independent set of digraph which includes the vertices of include and which does not include any vertices in exclude; if the argument size is supplied, then additionally the independent set will be required to contain precisely size vertices.

If include is not a independent set, then these functions return fail. Otherwise, the functions behave in the following way, depending on the number of arguments:

One or two arguments

If one or two arguments are supplied, then DigraphIndependentSet and DigraphMaximalIndependentSet greedily enlarge the independent set include until it can not continue. The result is guaranteed to be a maximal independent set. This may or may not return an answer more quickly than using DigraphMaximalIndependentSets (8.2-3). with a limit of 1.

Three arguments

If three arguments are supplied, then DigraphIndependentSet greedily enlarges the independent set include until it can not continue, although this independent set may not be maximal.

Given three arguments, DigraphMaximalIndependentSet returns the maximal independent set returned by DigraphMaximalIndependentSets(digraph, include, exclude, 1) if one exists, else fail.

Four arguments

If four arguments are supplied, then DigraphIndependentSet returns the independent set returned by DigraphIndependentSets(digraph, include, exclude, 1, size) if one exists, else fail. This independent set may not be maximal.

Given four arguments, DigraphMaximalIndependentSet returns the maximal independent set returned by DigraphMaximalIndependentSets(digraph, include, exclude, 1, size) if one exists, else fail.

gap> gr := ChainDigraph(6);
<digraph with 6 vertices, 5 edges>
gap> DigraphIndependentSet(gr);
[ 6, 4, 2 ]
gap> DigraphMaximalIndependentSet(gr);
[ 6, 4, 2 ]
gap> DigraphIndependentSet(gr, [2, 4]);
[ 2, 4, 6 ]
gap> DigraphMaximalIndependentSet(gr, [1, 3]);
[ 1, 3, 6 ]
gap> DigraphIndependentSet(gr, [2, 4], [6]);
[ 2, 4 ]
gap> DigraphMaximalIndependentSet(gr, [2, 4], [6]);
fail
gap> DigraphIndependentSet(gr, [1], [], 2);
[ 1, 3 ]
gap> DigraphMaximalIndependentSet(gr, [1], [], 2);
fail
gap> DigraphMaximalIndependentSet(gr, [1], [], 3);
[ 1, 3, 5 ]

8.2-3 DigraphMaximalIndependentSets
‣ DigraphMaximalIndependentSets( digraph[, include[, exclude[, limit[, size]]]] )( function )
‣ DigraphMaximalIndependentSetsReps( digraph[, include[, exclude[, limit[, size]]]] )( function )
‣ DigraphIndependentSets( digraph[, include[, exclude[, limit[, size]]]] )( function )
‣ DigraphIndependentSetsReps( digraph[, include[, exclude[, limit[, size]]]] )( function )
‣ DigraphMaximalIndependentSetsAttr( digraph )( attribute )
‣ DigraphMaximalIndependentSetsRepsAttr( digraph )( attribute )

Returns: A list of lists of positive integers.

If digraph is digraph, then these functions and attributes use CliquesFinder (8.1-2) to return independent sets of digraph. An independent set is defined by the set of vertices which it contains; see IsMaximalIndependentSet (8.2-1) and IsIndependentSet (8.2-1).

The optional arguments include and exclude must each be a (possibly empty) list of vertices of digraph, the optional argument limit must be either a positive integer or infinity, and the optional argument size must be a positive integer. If not specified, then include and exclude are empty lists, and limit is infinity.

The functions will return as many suitable independent sets as possible, up to the number limit. These functions will find independent sets which contain all of the vertices of include and which do not contain any of the vertices of exclude The argument size restricts the search to those cliques which contain precisely size vertices. If the function or attribute has Maximal in its name, then only maximal independent sets will be returned; otherwise non-maximal independent sets may be returned.

Let G denote the AutomorphismGroup (7.2-1) of the DigraphSymmetricClosure (3.3-9) of the digraph formed from digraph by removing loops and ignoring the multiplicity of edges.

Distinct independent sets

DigraphMaximalIndependentSets and DigraphIndependentSets each return a duplicate-free list of at most limit independent sets of digraph which satisfy the arguments.

The computation may be significantly faster if include and exclude are invariant under the action of G on sets of vertices.

Representatives of distinct orbits of independent sets

To use DigraphMaximalIndependentSetsReps or DigraphIndependentSetsReps, the arguments include and exclude must each be invariant under the action of G on sets of vertices.

If this is the case, then DigraphMaximalIndependentSetsReps and DigraphIndependentSetsReps each return a list of at most limit orbits representatives (under the action of G on sets of vertices) of independent sets of digraph which satisfy the arguments.

The representatives are not guaranteed to be in distinct orbits. However, if lim is not specified, or fewer than lim results are returned, then there will be at least one representative from each orbit of maximal independent sets.

gap> gr := CycleDigraph(5);
<digraph with 5 vertices, 5 edges>
gap> DigraphMaximalIndependentSetsReps(gr);
[ [ 1, 3 ] ]
gap> DigraphIndependentSetsReps(gr);
[ [ 1 ], [ 1, 3 ] ]
gap> DigraphMaximalIndependentSets(gr);
[ [ 1, 3 ], [ 1, 4 ], [ 2, 5 ], [ 2, 4 ], [ 3, 5 ] ]
gap> DigraphMaximalIndependentSets(gr, [1]);
[ [ 1, 3 ], [ 1, 4 ] ]
gap> DigraphIndependentSets(gr, [], [4, 5]);
[ [ 1 ], [ 2 ], [ 3 ], [ 1, 3 ] ]
gap> DigraphIndependentSets(gr, [], [4, 5], 1, 2);
[ [ 1, 3 ] ]
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 A Bib Ind

generated by GAPDoc2HTML