Maximum Clique

Given an undirected graph $G=(V,E)$ , a clique is a subset of vertices $C \subseteq V$ in which every pair of distinct vertices is connected by an edge.

More formally, for every pair of distinct vertices $u,v \in C$ ,

(u,v) \in E.

The goal of Maximum Clique is to find a clique containing the largest possible number of vertices.

Throughout this specification, Maximum Clique is abbreviated MC.

Before implementing your algorithms, review the project-wide Program Interface and Input Files specifications.

Graph Assumptions

MC instances use simple, unweighted, undirected graphs.

Vertices are numbered consecutively beginning with 0: $V=\{0,1,\ldots,n-1\}$ .
Graphs are not necessarily connected.
Isolated vertices may appear.

The standard unweighted graph formats and supplied input routines are described on the Input Files page.

Example

The same graph and its edge-list representation are shown side-by-side below. Filled vertices are members of one maximum clique.

Example graph                                  example-01.txt

       ● 0 ------- ● 1                               5 6
           \       /                                 0 1
            \     /       ● = in the clique          0 2
              ● 2         ○ = not in the clique      1 2
            /     \                                  2 3
           /       \                                 2 4
       ○ 3 ------- ○ 4                               3 4

The filled vertices represent the clique

C=\{0,1,2\}.

Every pair of vertices in $C$ is connected by an edge: $(0,1)$ , $(0,2)$ , and $(1,2)$ are all present.

This graph contains no clique of size 4, so $C$ is a maximum clique. The graph also contains another maximum clique, $\{2,3,4\}$ .

For comparison, $\{0,1,3\}$ is not a clique because vertices 0 and 3 are not adjacent.

MC Solution Format

MC uses maximum_clique as its project-wide problem identifier. The short command-line alias is mc.

The solution dictionary contains the vertices in the reported clique and the size of that clique:

{
  "size": 3,
  "vertices": [0, 1, 2]
}

The vertices list represents a set. Its order is not significant. Duplicate vertices are not permitted, and size must equal the number of entries in the list.

Using the common project interface,

python src/solve.py example-01.txt \
    --problem mc \
    --algorithm exhaustive

could produce a solution containing $[0,1,2]$ .

Your program is required to report only one maximum clique. If an instance has multiple maximum cliques, any one of them is acceptable; your program does not need to enumerate all optimal solutions.

Solution Verifier

Your Checkpoint 2 implementation must provide:

from course.common.graph import Graph


def is_clique(graph: Graph, vertices: list[int], k: int) -> bool:
    ...

in:

src/student/problems/maximum_clique/verifier.py

This is the verifier for the decision version of Maximum Clique. It returns True exactly when vertices forms a clique in graph containing at least k vertices.

For the example graph:

is_clique(graph, [0, 1, 2], 3)   # True
is_clique(graph, [0, 1, 2], 4)   # False
is_clique(graph, [0, 1, 3], 3)   # False: (0,3) is not an edge

A valid certificate must contain only vertices from the graph, with no duplicates, and every pair of distinct supplied vertices must be adjacent.

The verifier checks the supplied certificate. It does not determine whether that clique is maximum and must not call one of the solving algorithms.

Gradescope may import and test is_clique() independently of src/solve.py.

Checkpoint 2 Exhaustive Baseline

Checkpoint 2 uses the project-wide complete-candidate enumeration model. For Maximum Clique, a complete candidate is a subset of vertices.

A natural exact baseline considers candidate sizes from large to small, enumerates every subset of the current size, and sends each complete candidate to is_clique(). Once a valid candidate of size $k$ is found, it is optimal because every larger candidate size has already been exhausted.

The Checkpoint 2 baseline should not reject partial subsets, recursively grow only promising cliques, prune branches, or use branch-and-bound. Those are the kinds of improvements explored beginning in Checkpoint 3.

Checkpoint 3 Improved Exact Search

A natural improved exact strategy builds a clique incrementally. If C is the clique currently being constructed and P is the set of vertices that may still be added, every vertex in P must be adjacent to every vertex already in C.

After choosing a vertex v from P, a recursive search can continue with:

C' = C ∪ {v}
P' = (P - {v}) ∩ neighbors(v)

This immediately discards vertices that cannot extend the current clique. A simple branch-and-bound rule can also stop whenever the current clique plus all remaining candidates cannot improve the best clique already found.

These are examples rather than required implementations; your improved solver must remain exact and you must justify why any work it avoids cannot eliminate an optimal solution.

Checkpoint 3 Upper Bound

Maximum Clique is a maximization problem, so the required polynomial-time bound is an upper bound on the optimal clique size:

from course.common.graph import Graph


def upper_bound(graph: Graph) -> int:
    ...

in:

src/student/problems/maximum_clique/bound.py

If the optimum is $OPT$ , a valid result must satisfy

OPT \le \texttt{upper\_bound}(G).

There are several possible polynomial-time upper bounds. For example, $\Delta(G)+1$ is valid because a vertex in a clique of size $k$ has at least $k-1$ neighbors. A proper coloring also gives an upper bound because a clique can contain at most one vertex of each color.

You are not required to use either particular bound, but the returned value must be valid and computed in polynomial time.

Course Benchmark Suites

The supplied Maximum Clique benchmark manifest is located at:

benchmarks/maximum_clique/manifest.json

The required suites use the common experiment tool, for example:

python tools/run_experiments.py --suite exact_frontier
python tools/run_experiments.py --suite quality_known
python tools/run_experiments.py --suite heuristic_scale
python tools/run_experiments.py --suite structure

Exact frontier

The exact-search frontier contains three families with known optima:

balanced complete bipartite graphs — the maximum clique has size 2, so a large fraction of larger subsets must be rejected by the exhaustive baseline;
complete multipartite graphs with parts of size 3 — a maximum clique contains exactly one vertex from each part; and
two disconnected equal cliques — dense local structure combined with a complete absence of edges between the two components.

The default local exact-frontier timeout is 15 minutes per algorithm/instance. After an algorithm times out on one member of a frontier family, larger members of that same family are skipped for that algorithm.

The Gradescope timeout is intentionally shorter. Gradescope is a bounded automated check; the local CP4 frontier is where you investigate when your exact algorithm becomes impractical.

Heuristic scale

The scale suite uses sparse graphs containing a planted clique together with many independent distractor vertices. Required instances extend to 5,000 vertices while retaining a known optimum by construction.

Structural experiment

The required structural study holds both graph size and optimum fixed:

$n=300$ ;
$OPT=10$ .

Every instance is a complete 10-partite graph. The part-size distribution is changed to vary edge density while preserving the exact optimum. This lets you investigate whether density affects heuristic quality, runtime, variation across seeds, or the tightness of your upper bound without simultaneously changing problem size or the optimal clique size.

See:

benchmarks/maximum_clique/structure.md

for the full description.