Skip to content

Formulations of clique problems

Part 2 · Formulations and their properties · Chapter 12 · Lecture notes, volume 2 (PDF) · Slides · Exercises: Clique problems

Prerequisites

Objectives

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

  • write the edge formulation of the Maximum Clique Problem on the non-edges of \(G\), that is, on the edges of \(\overline{G}\);

  • explain why its LP relaxation is weak: the point \(x_v=\tfrac{1}{2}\) is always feasible;

  • write the clique formulation and compare the two LP bounds on a small graph;

  • prove \(\omega(G)\le z(\mathrm{LP}^{\mathrm{CL}}_{\mathrm{MCP}})\le\chi(G)\) through LP duality and a coloring formulation;

  • write the edge and the clique formulations of the Maximum Stable Set Problem;

  • write the ILP models of the vertex-weighted and of the edge-weighted maximum clique problems, linearizing the product \(x_u\,x_v\) with the variables \(y_{uv}\).

12.1 Overview of the family

  • The ILP models of the clique problems use one binary selection variable \(x_v\) for each vertex \(v \in V\), equal to \(1\) if the vertex is in the clique.

  • Two vertices that are not adjacent cannot be both selected: the conflict constraints are written on the non-edges of \(G\), that is, on the edges of the complement graph \(\overline{G}\), or on its cliques.

  • The objective function maximizes the number of selected vertices or their total weight; the edge-weighted problem adds one variable per edge.

The clique models select vertices with binary variables and forbid the selection of two non-adjacent vertices. The same models, written on the edges of \(G\) instead of \(\overline{G}\), select stable sets.

  • The table lists the members of the family, with the names of their ILP models and the sections that write them.
Problem Models Conflict constraints Section
MCP \(\mathrm{ILP}_{\mathrm{MCP}}\) (edge formulation) on the non-edges of \(G\) 12.2
MCP \(\mathrm{ILP}^{\mathrm{CL}}_{\mathrm{MCP}}\) (clique formulation) on the maximal stable sets of \(G\) 12.5
MSSP \(\mathrm{ILP}_{\mathrm{MSSP}}\), \(\mathrm{ILP}^{\mathrm{CL}}_{\mathrm{MSSP}}\) on the edges and the cliques of \(G\) 12.7
VWMCP \(\mathrm{ILP}^{\mathrm{VW}}_{\mathrm{MCP}}\) on the non-edges of \(G\) 12.8
EWMCP \(\mathrm{ILP}^{\mathrm{EW}}_{\mathrm{MCP}}\) on the non-edges of \(G\) 12.8

  • Overview

    Overview of the family

    Open

  • 12.2 An ILP model for the Maximum Clique Problem: the edge formulation

    A second Linear Programming relaxation · Clique inequalities: a stronger formulation · The relation with vertex coloring · Stable sets on the complement graph

    Open

  • 12.8 ILP models for the weighted variants

    The edge-weighted maximum clique problem · Typical mistakes · In summary

    Open

Next: 12.2 An ILP model for the Maximum Clique Problem: the edge formulation

Exercises on this chapter: Clique problems