Skip to content

Clique problems

Part 1 · Combinatorial optimization problems · Chapter 5 · Lecture notes, volume 1 (PDF) · Slides · Exercises: Clique problems

Prerequisites

Objectives

At the end of this chapter you will be able to:

  • state the maximum clique problem and the maximum stable set problem, and pass from one to the other through the complement graph;

  • describe an instance and a feasible solution, and count the candidate solutions of a small graph;

  • find a clique by hand and compute four simple upper bounds on the clique number;

  • state the weighted variants of the problem and its complexity.

5.1 Overview of the family

  • The clique problems share the same data: a simple undirected graph \(G = (V,E)\), with \(V = \{1,2,\dots,n\}\) and \(m\) edges, possibly with weights on the vertices or on the edges.

  • A solution is a clique of \(G\), that is, a subset of pairwise adjacent vertices.

  • The objective is to maximize the size of the clique, or its total weight.

Definition 5.1: clique and clique number

Let \(G=(V,E)\) be a simple undirected graph with \(n\) vertices and \(m\) edges.

  1. A clique is a subset \(K \subseteq V\) of pairwise adjacent vertices: \(\{u,v\} \in E\) for all \(u,v \in K\) with \(u \neq v\). Equivalently, \(K\) induces a complete graph.

  2. The clique number \(\omega(G)\) is the largest number of vertices of a clique of \(G\).

A clique problem selects a clique of maximum size or of maximum weight. On the complement graph \(\overline{G}\) the same problems select stable sets.

  • The table lists the members of the family, with the section that defines each of them.
Problem Acronym Objective Section
maximum clique problem MCP maximum number of vertices of a clique 5.2
maximum stable set problem MSSP maximum number of vertices of a stable set 5.2
vertex-weighted maximum clique problem VWMCP maximum total vertex weight 5.5
edge-weighted maximum clique problem EWMCP maximum total edge weight 5.5

  • Overview

    Overview of the family

    Open

  • 5.2 The maximum clique problem

    Simple upper bounds

    Open

  • 5.5 Weighted variants

    Typical mistakes · In summary

    Open

Next: 5.2 The maximum clique problem

Exercises on this chapter: Clique problems

In depth: what the course does on this problem