Skip to content

5.5 Weighted variants

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

  • Let \(\vet{w} \in \Z_{\ge 1}^n\) be a vertex-weight vector, with a weight \(w_v\) for each vertex \(v \in V\), and let \(\vet{r} \in \Z_{\ge 1}^m\) be an edge-weight vector, with a weight \(r_{uv}\) for each edge \(\{u,v\} \in E\). For a clique \(K\) we define

    \[ w(K) = \sum_{v \in K} w_v \qquad\text{and}\qquad r(K) = \sum_{\{u,v\} \in E[K]} r_{uv}, \]

    where \(E[K]\) is the set of the edges with both endpoints in \(K\).

Definition 5.10: weighted maximum clique problems

  1. Given a graph \(G\) and a vertex-weight vector \(\vet{w}\), the vertex-weighted maximum clique problem (VWMCP) asks to find a clique \(K\) of \(G\) with maximum total vertex weight \(w(K)\).

  2. Given a graph \(G\) and an edge-weight vector \(\vet{r}\), the edge-weighted maximum clique problem (EWMCP) asks to find a clique \(K\) of \(G\) with maximum total edge weight \(r(K)\).

  • With all the weights \(w_v=1\) the first problem is the MCP. The edge-weighted problem rewards the cliques with many heavy edges, and with \(r_{uv}=1\) it is again the MCP, since \(r(K)=\binom{|K|}{2}\) grows with \(|K|\).

Example 5.3: vertex-weighted maximum clique problem

We add to the graph of Example 5.2 the vertex weights in blue. The vertex-weighted maximum clique is \(\{2,3,5,8\}\), with weight \(8+9+6+9=32\): it is unique, and it is not the maximum clique in red of Example 5.2, whose weight is \(5+9+5+5=24\).

Figure 3

A clique takes at most one vertex from each pair \(\{1,5\},\{2,6\},\{3,7\},\{4,8\}\); taking the heavier one of each pair gives \(6+8+9+9=32\), and these four vertices form a clique.

Example 5.4: edge-weighted maximum clique problem

We add to the graph of Example 5.2 the edge weights in red. The edge-weighted maximum clique is \(\{2,5,7,8\}\), in orange: its six edges weigh \(6+4+9+7+3+8=37\), and the enumeration of the \(16\) maximum cliques shows that it is the unique optimal solution.

Figure 4

5.6 Remarks

  • In a coloring, every color class is a stable set: the MSSP is the problem of the largest color class, and the clique number is the dual bound of Chapter 4 «Coloring problems».

  • Applications of cliques and stable sets:

    • groups of pairwise connected members in social networks;

    • groups of pairwise compatible tasks or exams, in scheduling and in the planning of timetables;

    • common substructures of two molecules, in chemistry and in biology;

    • codes that correct errors, as large sets of words pairwise far apart.

5.7 Typical mistakes

Warning

  • Confusing a maximal clique with a maximum clique. A clique is maximal when no vertex can be added to it; it is maximum when no clique is larger. In Example 5.1, \(\{4,5\}\) is maximal but not maximum.

  • Building the complement graph with the edges of \(G\). The edges of \(\overline{G}\) are exactly the pairs that are not edges of \(G\): there are \(\binom{n}{2}-m\) of them.

  • Using a lower bound as an upper bound. A clique found by hand gives \(\LB \le \omega(G)\); the degree bounds and a coloring give \(\UB \ge \omega(G)\). In this chapter the problem is a maximization.

  • Believing that the coloring bound is tight. On the cycle with \(5\) vertices \(\omega(G)=2\) and \(\chi(G)=3\).

5.8 In summary

In summary

  • The MCP looks for the largest set of pairwise adjacent vertices; its optimal value is the clique number \(\omega(G)\).

  • A clique of \(G\) is a stable set of \(\overline{G}\): the MCP on \(G\) is the MSSP on \(\overline{G}\), and \(\omega(G)=\alpha(\overline{G})\).

  • A clique found by hand is a primal bound; the degree bound, the edge bound, the degree count bound and the number of colors of a coloring are dual bounds.

  • The MCP is NP-hard and hard to approximate; its weighted variants weigh the vertices or the edges.

Dashboard of the reference instances.

instance (max) lower bound upper bound from
Example 5.1 (cycle with a chord) \(3\) (by hand) \(3\) (degree count, coloring) this chapter
Example 5.2 (dense graph) \(4\) (by hand) \(4\) (coloring) this chapter

Exercises on this chapter: Clique problems

In depth: what the course does on this problem