Maximum stable set problem (MSSP)

Catalogue of combinatorial problems · Clique problems · Catalogue (PDF)

Definition 1: Maximum stable set problem

Let \(G=(V,E)\) be a graph.

1. A stable set (also called independent set) is a subset \(Q \subseteq V\) of pairwise non-adjacent vertices: \(\{u,v\} \notin E\) for all \(u,v \in Q\) with \(u \neq v\).

2. The Maximum Stable Set Problem (MSSP) asks to find a stable set of \(G\) whose number of vertices is maximum. Its optimal value is the stability number \(\alpha(G)\).

Assumptions

• We consider nontrivial instances: the graph has at least one edge and at least one non-edge. Formally:

  \[ 1 \le m < \binom{n}{2}. \]

• The assumption can be made without loss of generality: if the graph has no edge, every single vertex is a maximum clique and \(\omega(G)=1\); if the graph is complete, \(V\) itself is a clique and \(\omega(G)=n\).

What the course does on this problem

Technique	Where
Definition	Ch. 5 «Clique problems»
Formulations	Ch. 12 «Formulations of clique problems»
Limits of approximation	Ch. 38 «Maximum clique: limits of approximation»
Exercises	Exercise 4.3; Ch. 5 (2 exercises); Exercise 12.6; Ch. 38 (2 exercises)