This work builds upon Gump: A Good Approximation for Cliques.
The Maximum Clique Problem (MCP) is a classic NP-hard problem in graph theory and computer science. Given an undirected graph $G = (V, E)$, a clique is a subset of vertices $C \subseteq V$ where every two distinct vertices are connected by an edge. The goal of MCP is to find the largest possible clique in $G$.
The Maximum Clique Problem remains a fundamental challenge in computational complexity with broad practical implications. While exact methods are limited to small graphs, heuristic and hybrid approaches enable solutions for real-world applications.
Input: A Boolean Adjacency Matrix $M$.
Answer: Find a Maximum Clique.
| c1 | c2 | c3 | c4 | c5 | |
|---|---|---|---|---|---|
| r1 | 0 | 0 | 1 | 0 | 1 |
| r2 | 0 | 0 | 0 | 1 | 0 |
| r3 | 1 | 0 | 0 | 0 | 1 |
| r4 | 0 | 1 | 0 | 0 | 0 |
| r5 | 1 | 0 | 1 | 0 | 0 |
The input for undirected graph is typically provided in DIMACS format. In this way, the previous adjacency matrix is represented in a text file using the following string representation:
p edge 5 4
e 1 3
e 1 5
e 2 4
e 3 5
This represents a 5x5 matrix in DIMACS format such that each edge $(v,w)$ appears exactly once in the input file and is not repeated as $(w,v)$. In this format, every edge appears in the form of
e W V
where the fields W and V specify the endpoints of the edge while the
lower-case character e signifies that this is an edge
descriptor line.
Example Solution:
Clique Found 1, 3, 5: Nodes 1, 3,
and 5 constitute an optimal solution.
The find_clique algorithm offers a practical solution by
approximating a large clique. It processes each connected component of the
graph, using a fast triangle-finding method (from the
aegypti package) to identify dense regions. It iteratively
selects vertices involved in many triangles, reduces the graph to their
neighbors, and builds a clique, returning the largest one found. This
approach is efficient and often finds near-optimal cliques in real-world
graphs, making it valuable for practical applications. This novel approach
guarantees improved efficiency and accuracy over current method:
For details, see:
📖
The Aegypti Algorithm
pip install gump
Clone the repository:
git clone https://github.com/frankvegadelgado/gump.git
cd gump
Run the script:
fate -i ./benchmarks/testMatrix1
utilizing the fate command provided by Gump's Library to
execute the Boolean adjacency matrix
gump\benchmarks\testMatrix1. The file
testMatrix1 represents the example described herein. We
also support .xz, .lzma, .bz2,
and .bzip2 compressed text files.
Example Output:
testMatrix1: Clique Found 1, 3, 5
This indicates nodes 1, 3, 5 form a clique.
Use the -c flag to count the nodes in the clique:
fate -i ./benchmarks/testMatrix2 -c
Output:
testMatrix2: Clique Size 4
Display help and options:
fate -h
Output:
usage: fate [-h] -i INPUTFILE [-a] [-b] [-c] [-v] [-l] [--version]
Compute the Approximate Clique for undirected graph encoded in DIMACS format.
options:
-h, --help show this help message and exit
-i INPUTFILE, --inputFile INPUTFILE
input file path
-a, --approximation enable comparison with a polynomial-time approximation approach within a polynomial factor
-b, --bruteForce enable comparison with the exponential-time brute-force approach
-c, --count calculate the size of the clique
-v, --verbose anable verbose output
-l, --log enable file logging
--version show program's version number and exit
Batch execution allows you to solve multiple graphs within a directory consecutively.
To view available command-line options for the
batch_fate command, use the following in your terminal or
command prompt:
batch_fate -h
This will display the following help information:
usage: batch_fate [-h] -i INPUTDIRECTORY [-a] [-b] [-c] [-v] [-l] [--version]
Compute the Approximate Clique for all undirected graphs encoded in DIMACS format and stored in a directory.
options:
-h, --help show this help message and exit
-i INPUTDIRECTORY, --inputDirectory INPUTDIRECTORY
Input directory path
-a, --approximation enable comparison with a polynomial-time approximation approach within a polynomial factor
-b, --bruteForce enable comparison with the exponential-time brute-force approach
-c, --count calculate the size of the clique
-v, --verbose anable verbose output
-l, --log enable file logging
--version show program's version number and exit
A command-line utility named test_fate is provided for
evaluating the Algorithm using randomly generated, large sparse matrices.
It supports the following options:
usage: test_fate [-h] -d DIMENSION [-n NUM_TESTS] [-s SPARSITY] [-a] [-b] [-c] [-w] [-v] [-l] [--version]
The Gump Testing Application using randomly generated, large sparse matrices.
options:
-h, --help show this help message and exit
-d DIMENSION, --dimension DIMENSION
an integer specifying the dimensions of the square matrices
-n NUM_TESTS, --num_tests NUM_TESTS
an integer specifying the number of tests to run
-s SPARSITY, --sparsity SPARSITY
sparsity of the matrices (0.0 for dense, close to 1.0 for very sparse)
-a, --approximation enable comparison with a polynomial-time approximation approach within a polynomial factor
-b, --bruteForce enable comparison with the exponential-time brute-force approach
-c, --count calculate the size of the clique
-w, --write write the generated random matrix to a file in the current directory
-v, --verbose anable verbose output
-l, --log enable file logging
--version show program's version number and exit