<figure><img src="image_1.png" /></figure>

HAL
open science

# Coloring Constraint based on Lagrangian Relaxation

Hugo Apeloig

► To cite this version:

Hugo Apeloig. Coloring Constraint based on Lagrangian Relaxation. Operations Research [math.OC]. 2024. dumas-04936273

HAL Id: dumas-04936273

https://dumas.ccsd.cnrs.fr/dumas-04936273v1

Submitted on 8 Feb 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Master Operations Research and Combinatorial Optimization

Master Informatique / Master Mathématiques & Applications

Coloring Constraint based on
Lagrangian Relaxation

APELOIG Hugo

August 19, 2024

Research project performed at GSCOP

Under the supervision of:
Hadrien CAMBAZARD

Defended before a jury composed of:

Mrs Nadia BRAUNER

Mr Van-Dat CUNG

Mr Emmanuel HÉBRARD
<figure><img src="image_3.png" /></figure>
Abstract

The *k-coloring* problem is a very studied *NP-Hard* problem with multiple practical applications in partitioning and scheduling problems. In this context we study a *CP* constraint for the *list-coloring* problem, a generalisation of the *k-coloring* with a list of available colors for each vertex which is *NP-Hard* on chordal graphs.

We propose a constraint based on the *Lagrangian relaxation of list-coloring* for chordal graphs. This *Lagrangian relaxation* requires to address the *maximum weighted independent set* problem. We show that *arc-consistency* for *MWIS* can be achieved in $O(|Q|m)$ where $m$ is the number of edges of the graph and $|Q|$ is related to the number of maximal cliques which is bounded by $n$ for chordal graph. We also give an algorithm bounding the *chromatic list number* on chordal graph which succeed where the classical model reaches memory limits.

Résumé

Le problème *k-coloring* est un problème *NP-Hard* très étudié avec de nombreuses applications pratiques dans les problèmes de partitionnement et d'ordonnancement. Dans ce contexte, nous étudions une contrainte *CP* pour le problème *list-coloring*, une généralisation du problème *k-coloring* avec une liste de couleurs disponibles pour chaque sommet qui est *NP-Hard* sur les graphes chordaux.

Nous proposons une contrainte basée sur la *relaxation Lagrangienne* de *list-coloring* pour les graphes chordaux. Cette *relaxation Lagrangienne* nécessite de résoudre le problème de *maximum weighted independent set*. Nous montrons que l'arc-consistency pour le *MWIS* problème peut être obtenue en $O(|Q|m)$ où $m$ est le nombre d'arêtes du graphe et $Q|$ est lié au nombre de cliques maximales qui est limité par $n$ pour les graphes chordaux. Nous donnons également un algorithme bornant le *chromatic list numbers* sur les graphes chordaux qui fonctionne dans les cas où le modèle classique atteint les limites de mémoire.
<figure><img src="image_4.png" /></figure>
# Contents

Abstract i

Résumé i

1 Introduction 1

2 Background 3

2.1 Constraint Satisfaction Problem 3

2.2 Graphs and Coloring 4

2.3 IP, LP and Marginal Costs 8

2.4 Lagrangian Relaxation 8

3 Coloring Constraint 11

3.1 Global Reasoning 12

3.2 Constraint Programming for *k-coloring* 13

3.3 Model Application 14

4 LP Models for List-Coloring 15

4.1 Independent sets 15

5 Lagrangian Relaxation 19

6 Filtering: Chordal Case 21

6.1 Frank Algorithm 21

6.2 Clique Tree Decomposition 28

6.3 Perfect Graphs Extension 28

7 Filtering Algorithm for COLORING 31

8 *List-Coloring* Complete Resolution Process 33

9 Benchmarks and Experimental Results 35

9.1 Benchmarks 35

9.2 Results 35
<table><tr><td>10 History of Coloring and its Industrial Uses</td><td>41</td></tr><tr><td>11 Exercises for the ORCO Program</td><td>43</td></tr><tr><td>12 Conclusion</td><td>45</td></tr><tr><td>Bibliography</td><td>47</td></tr><tr><td>A APPENDIX</td><td>51</td></tr><tr><td>A.1 Filtering based on a maximal clique-tree decomposition</td><td>51</td></tr><tr><td>A.2 Frank's Algorithms</td><td>54</td></tr><tr><td>A.3 Example of Honours and Subjects Instance</td><td>55</td></tr><tr><td>B ORCO Exercise</td><td>57</td></tr></table>
Introduction

The *List-Coloring* problem is a generalisation of the graph coloring problem [21]. It is an *NP-Hard minimization* problem with multiple practical applications in scheduling and allocation problems [18].

In this internship we are interested in reasoning on the *list-coloring* problem from a *constraint programming* point of view. We propose a *global constraint COLORING* with its filtering algorithm. The filtering relies on a lower bound for the *chromatic number*. In this regard, we investigate a *Lagrangian relaxation* for *list-coloring*. This relaxation requires to address the *maximum weighted independent set (MWIS)* problem. Therefore, we focus on reasoning for the *maximum weighted independent set* problem. A key contribution is to deal with the case where *G* is chordal. We show that *arc-consistency* for *MWIS* can be achieved in *O(|Q|m)* where *m* is the number of edges of the graph and *|Q|* is related to the number of maximal cliques which is bounded by *n* for chordal graph.

We support our results on *MWIS* with an empirical study on multiple classes of chordal graphs [37]. A preliminary version of the *COLORING* constraint is implemented in the *ChocoSolver* [34] but remains restricted to chordal graphs so far. In Section 8, we give an algorithm for *list-coloring* using an exponential formulation in *Integer Programming*. The variables of this model are based on the *independent sets* obtained by *Lagrangian relaxation*. We show and discuss cases where it outperforms classical *MIP* models. This is the second contribution of this internship.

Firstly, an overview of the background as well as notions and key concepts is given. Secondly, the global constraint *COLORING* is presented. We then investigate the lower bound of the *chromatic number* based on the *Lagrangian relaxation*. The filtering of *maximum weighted stable set* on chordal graphs is shown in Section 6. Afterwards, we explain filtering algorithm for *COLORING* as well as our complete resolution process for the *list-coloring* problem. Implementation results are given in Section 9. Finally, we present a teaching content using several notions of this internship as well as an historical review of the *coloring* problem and its industrial uses.
<figure><img src="image_5.png" /></figure>
2

Background

2.1 Constraint Satisfaction Problem

A constraint satisfaction problem (CSP) is a triple (X, D, C) with X a set of variables, D the corresponding domains and C a set of constraints [25]. Each variable x ∈ X has a set of possible values D (x). The lower bound of x (i.e the lowest value in D (x)) is noted x and the upper bound is noted x̄. A constraint c ∈ C is a pair (X_c, P_c) where X_c ⊆ X is the scope (i.e the variables seen by the constraint) and P_c is a predicate. An assignment A is a mapping from each x ∈ X to a value in D (x) (a partial assignment is an assignment over a subset of X). If P_c(A) is satisfied, then the assignment A is a support for the constraint c. A CSP is satisfied by A (an assignment on X) if every constraint of C is satisfied by A. Finding whether a valid assignment exists (and determining its values) to a given CSP is NP-Complete.

A value v ∈ D (x) is called arc consistent with a constraint c if x ∈ X_c and there exists a support (a satisfying assignment) A of c such that A(x) = v (i.e v is the value given to x in assignment A). A constraint c is called domain consistent (or generalized arc consistent) if for every x ∈ X_c and for all v ∈ D (x), v is arc-consistent with c. For example, the constraint ALLDIFFERENT(X) ensures that all variables take distinct values. More formally, a value of D (x) is arc-consistent if it belongs to an assignment A such that ∀x_i, x_j ∈ X, A(x_i) ≠ A(x_j). In figure 2.1 we can see an example of a domain before and after enforcing arc-consistency of such a constraint.

<figure><img src="image_6.png" /><figcaption>Figure 2.1: Example of arc-consistent domains for the ALLDIFFERENT constraint</figcaption></figure>

For each constraint c, domain consistency can be achieved by removing inconsistent values from the domains. In order to do so, constraints are defined with propagators that use algorithms to prune the domains in order to reach either a domain consistent fix point or a proof that no assignment can satisfy at least one constraint after propagation.
The *arc-consistency closure* of a CSP problem is reached when every domain of $\mathcal{D}$ is arc-consistent with every constraint of $\mathcal{C}$.

Once *arc-consistency closure* of a problem is obtained, CSP solvers can use different methods to solve it. In this paper we will consider *backtracking search*. The *branching* consist in either assigning a variable to one of its available value or to remove it from its domain. The resulting branching tree is binary: a decision is made leading to a sub-tree (e.g $x = v$) and its negation is enforced ($x \neq v$) upon backtracking leading to the other sub-tree. Each time a decision is made (i.e at each node of the branching) the solver propagates each constraint in order to enforce consistency. Whenever it fails (either a domain becomes empty or a contradiction appears), the decision and its sub-tree are removed from the search tree.

## 2.2 Graphs and Coloring

### Key concepts

In order to properly introduce our subject we will give useful definitions, notations and characterisations on graphs.

A graph $G = (V, E)$ is defined over a set $V$ of vertices and a set $E$ of edges. Given a vertex $v \in V$, $N(v) \subseteq V$ is its neighborhood (i.e the set of adjacent vertices in $G$).

Let $U \subseteq V$ be a subset of vertices of $G$. $U$ is a *Clique* if and only if $\forall u, v \in U, uv \in E$. Conversely, $U$ is an *independent set* (or *stable set*) iff $\forall u, v \in U, uv \notin E$. Later on, independent sets (resp. cliques) are sometimes indexed by (resp. q). In this case, $V(s)$ (resp. $V(q)$) is used to denote the set of vertices. In figure 2.2, $\{C, F, G\}$ is a *clique* of size 3 and $\{H, E, B, G\}$ is an *independent set* of size 4.

$\overline{G} = (V, \overline{E})$ is the complementary graph of $G$. It is defined over the same set of vertices $V$. For each pair of *non-adjacent* vertices in $G$, $\overline{G}$ contains an edge between them and there is no edge in $\overline{G}$ for each pair of adjacent vertices in $G$. Formally, $\forall uv \in E, uv \notin \overline{E}$ and $\forall uv \notin E, uv \in \overline{E}$. Note that an *independent set* of $G$ is a *clique* of $\overline{G}$ (and conversely), also, the *complementary* of $\overline{G}$ is $G$ itself.

In a graph $G$, a vertex $v$ is *simplicial* if and only if its neighborhood in $G$ is a clique. A perfect elimination ordering (*peo*) is an ordering of $V$ such that for all $v$, its neighborhood that occurs after it in this order form a clique ($i.e O = \{v_1, \dots, v_n\}$ an ordering of $V$ is a *peo* of $G$ iff $\forall v_i$, the graph induced by $N(v_i) \cap \{v_i+1, \dots, v_n\}$ is a clique).

A tree decomposition of a graph $G$ is a collection $\mathcal{T}$ of *bags* (i.e subsets of $V$) connected into a tree $T$ such that: each vertex of $G$ is in a bag; for each edge of $G$, both endpoints are in a bag; and for each vertex $v$ of $G$, the nodes of $T$ whose bags contain $v$ form a sub-tree. An example can be seen in figure 2.2 (b). A particular tree decomposition that will be seen in the present work is a *clique tree* decomposition of $G$. It is a valid *tree decomposition* in which each graph induced by a bag of $T$ is a clique in $G$.
<figure><img src="image_7.png" /><figcaption>Figure 2.2: Example of a Graph with its tree-decomposition</figcaption></figure>

A chordal graph contains no induced cycles of size four or more without a chord (similarly, all induced cycle are of size at most three). Chordal graphs are also characterised by the following equivalence: G is chordal iff G has a perfect elimination ordering. Numerous known NP-Hard problems on general graphs are known to be polynomially solvable on chordal graphs such as k-coloring or Maximum Weighted Independent Set. Another characterisation of chordal graphs is that there exists a Clique-Tree decomposition. Chordal graphs are hereditary, it means that each induced sub-graph of a chordal graph will itself be chordal.

<figure><img src="image_8.png" /><figcaption>Figure 2.3: Example of chordal Graph with one of its peo</figcaption></figure>

Chordal graphs are perfect graphs. A perfect graph is defined as a graph with no induced odd-cycle. An induced odd-cycle is a cycle with an odd number of vertices without any chord. Let $\omega(G)$ be the size of the maximum clique in G, G is perfect iff $\omega(G) = \chi(G)$. Also, G is perfect iff $\bar{G}$ is perfect. We define $\mathcal{Q}$, the set of all maximal cliques of G. Recall that, when G is chordal, $|\mathcal{Q}| < n$.

In a maximization (resp. minimization) problem (e.g finding a maximum independent set of G), the marginal cost of a variable $x_i$ is the difference between the optimal value $z_i^*$ and the optimal value $z_i^*$, one of the best solution that contains $x_i$. It can be seen as the price to enforce $x_i$ to be a part of the solution. Consider example 2.2 and the problem of finding an independent set of maximum size. An optimal solution would be $\{H, E, B, G\}$ whose size is 4. As an independent set containing C is at most of size 3, the marginal cost of $x_C$ would be -1. Marginal costs of variables will be used in this internship in the filtering algorithm.
# Coloring problems

Given a graph $G = (V, E)$, a well-known NP-Complete problem is the *k-coloring* problem defined as follow:

**k-Coloring**

**Instance.** A graph $G = (V, E)$

**Question.** Is there an assignment $\varphi$ on $V$ such that $\forall u \in V, \varphi(u) \in \mathbb{N}_+^*, \forall uv \in E, \varphi(u) \neq \varphi(v)$ and $\max_u(\varphi(u)) \le k$?

The problem is to find a coloring of $G$ with at most $k$ colors such that no adjacent vertices share the same color [29]. Such coloring of $G$ is called a proper coloring. The minimum number of colors needed to obtain a proper coloring of $G$ is named the *chromatic number* $\chi(G)$. On a practical point of view, multiple applications require $n$ items into a minimum number of subsets of compatible elements. We can cite, for example, the problem of partitioning frequently-accessed variables in compilers or the frequency assignment problem [24]. In [3], authors define a *conflict graph* to model wireless network frequency assignment with interference. In that model, vertices represent transmitter/receiver units and an edge means that both units are at the same emplacement (leading to interference). The problem consists in finding the minimal number of distinct frequencies (i.e colors) such that all units sharing the same emplacement use different frequencies.

In this context we are looking at a more general problem where each vertex of $G$ is mapped to a list $\mathcal{L}$ where $\mathcal{L}_i|v_i \in V$ is the list of possible colors (i.e values) that $v_i$ can take. The *List-coloring problem* ask for an assignment $\varphi(v_i) \in \mathcal{L}_i$ such that $\varphi(V)$ is a proper coloring of $G$. The *List-Coloring problem* can be formulated as follow:

**List-Coloring**

**Instance.** A graph $G = (V, E)$, a list $\mathcal{L}_i \subset \mathbb{N}, \forall v_i \in V$.

**Question.** Is there an assignment $\varphi$ on $V$ such that $\varphi(v_i) \in \mathcal{L}_i$ and $\forall uv \in E, \varphi(u) \neq \varphi(v)$?

First, one can easily check that our problem is *NP-Complete* by reducing it to the *k-coloring* problem. Taking the special case of *list-coloring* where we have $\mathcal{L}_i = \{1, \dots, k\}$ for all $\mathcal{L}_i$, *list-coloring* is equivalent to *k-coloring* and thus, *NP-Complete*. The *chromatic number* of $G$ with *list* is noted $\chi(G, \mathcal{L})$.

*List-coloring* is a generalisation of *coloring* and it also generalises others coloring problem such that *Precoloring Extension* (PrExt) [29]. This problem can be formulated as follow [7, 26, 27]:

**PrExt**

**Instance.** An integer $k \ge 1$, a graph $G = (V, E)$ with $|V| \ge k$, a subset of vertices $W \subseteq V$, and a proper *k-coloring* $\varphi$ of $G_W$.

**Question.** Can $\varphi$ be extended to a proper *k-coloring* of the entire graph $G$?

The *List-Coloring* generalizes *PrExt*, it is therefore *NP-Hard* in cases where *PrExt* is *NP-Hard* [16]. The *k-coloring* problem can be solved in polynomial time (and space) on perfect graphs, chordals or intervals graphs but, *list-Coloring* is known to be *NP-Complete* even under those conditions [8]. Another remark is that for the *k-coloring* problem ($\forall v_i \in V, \mathcal{L}_i = \mathcal{L}$ and $\mathcal{L}$ contains no holes), whenever $|\mathcal{L}| \ge \chi(G)$ (i.e $k \ge \chi(G)$)
<figure><img src="image_9.png" /><figcaption>Figure 2.4: Instance for List-Coloring on example 2.2</figcaption></figure>

then a proper coloring of $G$ exists. However in the case of list-coloring, even if $|\mathcal{L}_i| \ge \chi(G)$, $\forall v_i \in V$ the instance can be infeasible (see fig 2.5). However, in [16] it has been shown that 2-Regular List-Coloring is polynomial-time solvable for general graphs. In this restricted version of the problem each vertex have a list of available color whose size is exactly 2.

<figure><img src="image_10.png" /><figcaption>Figure 2.5: An Unfeasible instance of list-coloring where $G$ is bipartite ($\chi(G) = 2$) and $|\mathcal{L}_i| = 2, \forall v_i \in V$ (from [31])</figcaption></figure>

In this internship, we will use two other problems defined as follow [20].

**Hitting Set**

**Instance.** A collection $C$ of subsets of finite set $S$, a positive integer $K \le |S|$.

**Question.** Is there a subset $S' \subseteq S$ with $|S'| \le K$ such that $S'$ contains at least one element from each subset in $C$ ?

Hitting Set is NP-Complete even if $|c| \le 2$ for all $c \in C$.

**Weighted Independent Set**

**Instance.** A graph $G = (V, E)$, a weight $w(v) \in \mathbb{R}_+$, $\forall v \in V$, a positive real $r$.

**Question.** Does $G$ contain an *independent set* $S$ such that $\sum_{v \in S} w(v) \ge r$.

*Weighted Independent Set* is *NP-Complete* on general graphs and can be solved in polynomial time and space on *chordal* graphs.
## 2.3 IP, LP and Marginal Costs

Linear programming is often used to provide lower bounds. We seek a way to compute a lower bound of list-coloring to approximate the marginal costs of variables. Let's therefore recall the basic concepts.

A linear programming notion used in this internship is the principle of reduced cost of a variable. It is a lower bound of the marginal cost. Let an IP model defined as:

$$ \begin{array}{llll} \min & z = cx & & \\ \textbf{(P)} & \text{s.t} & Ax & \geq b, \\ & & x & \in \mathbb{N} \end{array} \qquad (2.1) $$

In Integer Programming, a way to approximate a solution (i.e to bound a minimization problem from below) is to use a relaxation over one or more constraints. The most well-known relaxation consists in relaxing the integrality of each domain, the linear relaxation. For example, (P) is defined over integer variables ($x \in \mathbb{N}$) and the linear relaxation of (P) is defined over positive real variables ($x \ge 0$).

In linear programming the reduced cost $\bar{rc}(x_i)$ of a variable $x_i$ can be obtained using the dual problem of P. It is defined as:

$$ \begin{array}{llll} \max & v = yb & & \\ \textbf{(D)} & \text{s.t} & yA & \leq c, \\ & & y & \geq 0 \end{array} \qquad (2.2) $$

From a dual feasible solution of (D), the reduced cost of each variable can be computed with $\bar{rc}(x_i) = c_i - yA_i$, with $A_i$ the coefficients of the variable $x_i$ in the constraints of (P). Whenever the reduced cost of $x_i$ is equals to its marginal cost, $\bar{rc}(x_i)$ is called the exact reduced cost.

## 2.4 Lagrangian Relaxation

The Lagrangian relaxation of a problem is a way to simplify a problem by relaxing a constraint in the objective function and by paying a corresponding cost for its violation [40]. Once solved, the Lagrangian sub-problem of a minimization (resp. a maximization) problem provides a lower bound (resp. an upper bound) of the optimal solution value. Consider the following IP problem defined over the set $X$ (typically, $X = \mathbb{N}$):

$$ \begin{array}{llll} \min & z = cx & & \\ \textbf{(P}_2) & \text{s.t} & Ax & \geq b, \\ & & Dx & \geq d, \\ & & x & \in X \end{array} \qquad (2.3) $$

Suppose that constraints $Ax \ge b$ are considered as easy constraints (i.e can be efficiently solved) and $Dx \ge d$ being the complicated constraints. The Lagrangian sub-problem of $\mathbf{P}_2$ is defined with fixed $\lambda \ge 0$ over the set of variables $X$.

$$ \begin{array}{llll} \min & z(\lambda) = cx + \lambda(d - Dx) & & \\ \textbf{(P}_2(\lambda)) & \text{s.t} & Ax & \geq b, \\ & & x & \in X \end{array} \qquad (2.4) $$
The Lagrangian dual is the problem of finding the $\lambda$ values that maximize the objective value of the Lagrangian sub-problem. It is defined as:

$$ (\mathbf{LD}) \quad \max_{\lambda \ge 0} \min_{x \in X} z(\lambda) = cx + \lambda(d - Dx) \qquad (2.5) $$

The Lagrangian dual (LD) is equivalent to a maximization problem of a piecewise linear function. It is not differentiable but it can be solved with a sub-gradient algorithm [40]. This algorithm moves in the space of the lambda variable. At each iteration it assigns values to lambda. From a mathematical point of view, at each iteration $t$, we move from the current point $\lambda^t$ in the opposite direction of a sub-gradient with a given step length $\mu^t$.

$$ (\text{Subgradient}) \quad \lambda^{t+1} = \lambda^t + \mu^t(d - Dx(\mu^t)) $$

At each step $\lambda^{t+1}$ must be positive (i.e verify $\lambda^{t+1} = \max(\lambda^{t+1}, 0)$). The step length function must converge to 0 for the algorithm to stop properly.

In this internship, two different gradient algorithms from [40] are used, refereed as Geometric and Newton. They update $\mu^t$ with respectively:

$$ (\text{Geometric}) \quad \mu_t = \mu_0 * q^t, \quad 0 < q < 1 $$

$$ (\text{Newton}) \quad \mu_t = \frac{\mu_0}{2^{\frac{t}{10}}} * \frac{(\bar{w} - \underline{z}_t)}{(d - Dx)^2} $$

with $\mu_0$ and $q$ depending on the instance size. In (Newton), $\bar{w}$ is an upper bound of $z$ and $\underline{z}_t$ is best lower bound at time $t$.

This Lagrangian relaxation can be used in order to remove values that can not belong to an optimal solution. First an upper bound $\bar{z}$ of $z^*$ is efficiently calculated (with heuristics or approximation). As the Lagrangian dual gives at all time a lower bound $\underline{z}$ of the optimal value, if $\overline{rc}(x_i)$ can efficiently be calculated for $P_2(\lambda)$ then for each $x_i$, if $z^*(\lambda) + \overline{rc}(x_i) > \bar{y}$, it means that $x_i$ does not appear in an optimal solution.

Lagrangian relaxation can also be used in order to filter the domains of variables in constraint programming following the same method and has already been used [9, 12].
<figure><img src="image_11.png" /></figure>
3

Coloring Constraint

In this internship, we propose a global constraint that given a graph and a domain for each vertex ensures that a proper *list-coloring* exists with an upper bound *y* on the number of different colors used.

$$
\text{COLORING}(\mathcal{X} = [x_1, \dots, x_n], y, G)
$$

It is defined over the set of *integer variables* $\mathcal{X}$, the *integer variable* $y$ and the graph $G = (V, E)$. A variable $x_i$ is related to vertex $v_i \in V$ of $G$ and gives the color assigned to $v_i$. Variable $y$ is an upper-bound of the *list chromatic number* of $G$ and a sharp *lower bound* $\bar{y}$ is given by $\chi(G, \mathcal{L})$. **A valid support for this constraint is a proper list-coloring of G of at most $\bar{y}$ colors.**

Take for example the graph *G* with the corresponding domains in figure 2.4. Let *y* be an integer variable representing an upper-bound of the *list chromatic number* of *G*. Take for exemple *D*(*y*) = {1, 2, 3, 4}. The constraint *COLORING*(*X* = [*x*<sub>A</sub>, *x*<sub>B</sub>, *x*<sub>C</sub>, *x*<sub>D</sub>, *x*<sub>E</sub>, *x*<sub>F</sub>, *x*<sub>G</sub>, *x*<sub>H</sub>], *y*, *G*) ensure that *y* the lower bound of *y* is at least the minimum number of colors needed to proper color *G* with respect to the domains. *Arc-consistent* domains are shown in figure 2.4. Note that *y* is 4 and a solution could be {*x*<sub>A</sub> = 4, *x*<sub>B</sub> = 1, *x*<sub>C</sub> = 3, *x*<sub>D</sub> = 1, *x*<sub>E</sub> = 3, *x*<sub>F</sub> = 2, *x*<sub>G</sub> = 4, *x*<sub>H</sub> = 2, *y* = 4}.

<figure><img src="image_12.png" /><figcaption>Figure 3.1: Comparison of COLORING *arc-consistent* domains and (*DEC*) *arc-consistency closure* for example 2.4</figcaption></figure>
<figure><img src="image_13.png" /><figcaption>Figure 3.2: Decomposed CP model for example 2.4</figcaption></figure>

The COLORING($\mathcal{X}$, $y$, $G$) constraint is equivalent (i.e has the same set of solution) to the following constraint network.

**Decompose Model (DEC):**

$$x_i \neq x_j, \qquad \forall (ij) \in E \quad (3.1)$$

$$\text{ATMOSTNVALUES}([x_1, \dots, x_n], y) \qquad (3.2)$$

$$x_i \in D(x_i), \qquad \forall i = 1, \dots, n \quad (3.3)$$

$$y \in \mathbb{N} \qquad (3.4)$$

For a given graph $G$, with the model DEC there is $|E| + 1$ constraints. Constraints (3.1) ensure that for each edge of $G$, the two endpoints takes a different value. The constraint ATMOSTNVALUE($\mathcal{X}$, $y$) is a NP-Hard global constraint which restricts the maximum number of distinct values taken by the set $\mathcal{X}$ to at most $y$ [5]. The Decomposed model for the example 2.4 is written in figure 3.2.

From this model we observe that *list-coloring* is equivalent to the Hitting Set problem when the graph $G$ contains no edges. As a result:

**Lemma 1.** *Generalized arc consistency is NP-Hard for the coloring constraint even on graphs with no edges.*

The difference with DEC is the reasoning made over the domains. Comparison of *arc-consistent* domains for COLORING and *arc-consistency closure* of DEC on the example 2.4 is shown on figure 3.1.

## 3.1 Global Reasoning

Multiple global reasoning can be applied in order to improve DEC. In practice, the challenge of efficiently solve the *list-coloring* problem can be more related to the graph characteristics, or to the *Hitting Set* problem resulting from the lists or both.

From a graph point of view, $\chi(G)$ is one of the most efficient lower bound. A first reasoning on $G$ can be made using cliques. Each *clique q* of $G$ (whose size is greater than two) can be seen as an ALLDIFFERENT constraint over $V(q)$. Note that an ALLDIFFERENT on the *maximal* cliques of $G$ is enough and more efficient.

In cases where $\chi(G)$ can be efficiently computed (e.g $G$ is chordal) the hardness of the problem will be more related to the lists of colors. Since the *linear relaxation* of *list-coloring* is equivalent to the linear relaxation of the *Hitting Set* problem on the lists,
<figure><img src="image_14.png" /><figcaption>Figure 3.3: Example of Zykov recurrence on example 2.2</figcaption></figure>

efficient filtering and reasoning on ATMOSTNVALUE can provide an efficient lower bound. A Lagrangian based filtering has already been studied [12] and successfully implemented. Note that, when G is empty (i.e has no edges), the COLORING constraint is equivalent to ATMOSTNVALUE.

Take G and $\mathcal{L} = \{\mathcal{L}_A, \dots, \mathcal{L}_H\}$ defined in example 2.4. Consider the Constraint Programming corresponding variables and domains in figure 3.1. First, the subset $\{C, F, G\}$ forms a clique of size 3 in G and by applying an ALLDIFFERENT($\mathcal{X} = [x_C, x_F, x_G]$), the value 2 can be removed from $D(x_C)$. Then as $\{A, B, C, D, E\}$ forms an odd-cycle, values 1 and 3 can be removed from $D(x_A)$. Finally, constraint ATMOSTNVALUES will filter values 1, 2 and 3 form $D(y)$ and as $\bar{y} = 4$, value 5 will be removed from $D(H)$.

## 3.2 Constraint Programming for k-coloring

In 2020 in [25], authors have proposed a constraint programming approach for k-coloring with a branching scheme based on Zykov's recurrence [2]. In contrast to branching on colors, Zykov's recurrence branch on equality/difference between non-adjacent vertices. It is defined as following: take $G = (V, E)$ a graph and $u, v \in V$ such that $uv \notin E$. Let $G/(uv)$ be the graph obtained by contracting u and v (a unique vertex replaces u and v and is connected to both neighborhood) and $G + (uv)$ the graph obtained by adding the edge $(uv)$. Then we have:

$$ \chi(G) = \min\{\chi(G/(uv)), \chi(G + (uv))\} $$

The proof resides in the fact that in an optimal coloring of G, either u and v have the same color (then $\chi(G) = \chi(G/(uv))$) or a distinct one ($\chi(G) = \chi(G + (uv))$). Branching on this method cannot not reduce the maximum clique $\omega(G)$ size. Therefore, at each node of the tree-search, this lower bound cannot decrease. Figure 3.3 depicts the branching results on example 2.2 for the pair of vertices $(A, D)$.

### Extension to COLORING($\mathcal{X}, \mathcal{E}, y, G$).

For each tuple of vertices $(u, v) \in V^2$, let $e_{uv} \in \mathcal{E}$ be the boolean variable representing if u and v are adjacent. Formally, $e_{uv} \in \{0, 1\}$ and $e_{uv} = 1$ if $uv \in E$ (i.e $e_{uv} = 0$ if $uv \notin E$). COLORING can be extended in order to react to assignment over the variables of $\mathcal{E}$ (i.e to the modifications of G) during the branch and bound solving process.
3.3 Model Application

Timetabling scheduling using a graph coloring approach leads to efficient results [18]. Their idea is to efficiently transform scheduling problems into instances of k-coloring or list-coloring and then use already defined efficient methods or models to solve them. In this context, a COLORING constraint could be useful.

Let for example the problem of Honours and General subject combination<fnref n="1" />. The
problem is to find a minimum number of time slots to schedule a list of lessons with
respect to certain constraints. The problem is transformed into a *k*-coloring problem
with the following strategy. Let *G* = (*V*, *E*) be such that, for each course *i*, *v*ᵢ ∈ *V* is the
vertex representing it. For each pair of courses (*i*, *j*) having students and/or teachers in
common, *ij* ∈ *E* represents the no overlapping condition. Others conditions can lead to a
no overlapping constraint between two courses, in such case, an edge is also added. Then
the total number of colors available is defined by the maximum duration achievable (*i*.e
the number of hours available in a week or a day). Then, χ(*G*) represent the minimum
number of slots needed.

In a variant of this problem, certain courses also have exterior constraint that withdraw particular slots. In such case, the problem becomes a *list-coloring* problem.

<footnote n="1">¹see Appendix A.3 for an example.</footnote>
— 4 —

LP Models for List-Coloring

The linear relaxation of integer programming formulations can be used to obtain a lower bound on $\chi(G, \mathcal{L})$. We define two models for list-coloring.

Let's start with a basic compact IP formulation. It relies on variables $y_c$ the decision (boolean) to use or not the color $c$ and $x_{ic}$ the decision (boolean) variable to assign color $c$ to vertex $v_i$.

$$ (\mathbf{P}) \quad \begin{array}{ll} \text{minimize} & \displaystyle\sum_{c \in \bigcup_{i \in V} C_i} y_c \end{array} \qquad (4.1a) $$

$$ \text{subject to} \quad \sum_{c \in C_i} x_{ic} = 1, \quad \forall i \in V, \qquad (4.1b) $$

$$ x_{ic} + x_{jc} \le y_c, \quad \forall c \in C_i \cap C_j, \quad \forall (i, j) \in E, \qquad (4.1c) $$

$$ x_{ic} \in \{0, 1\}, \quad \forall i \in V, \quad \forall c \in C_i, \qquad (4.1d) $$

$$ y_c \in \{0, 1\}, \quad \forall c \in C_i \qquad (4.1e) $$

The objective of (P) is to minimize the sum of $y_c$ with the constraints that only one color is used for each vertex (4.1b) and that for each edge, the two endpoints must have different colors (4.1c). The difference with the k-coloring problem lies in the domain $C_i$ which is the set of colors available for vertex $v_i$.

The fact that we consider list-coloring creates a difference on the symmetry. In k-coloring, having a solution with colors $c_1, c_2, c_3$ was the same as a solution with $c_1, c_2, c_8$ and a possible way to break symmetry was to add a constraint $y_{c_i} >= y_{c_j}$ with $i < j$. This way an exponential number of solution where removed. In the List-Coloring problem the previous constraint is no more valid. Similarly, the linear relaxation of problem (P) in the case of complete domains is always 1 [28]. In the case of list-coloring the linear relaxation (LRP) solution becomes list dependant.

**Observation 1.** LP relaxation of (P) is 1 if for each vertex $v_i \in V$, $\mathcal{L}_i = [1, \dots, k]$.

## 4.1 Independent sets

Another formulation for list-coloring is based using Stable sets. A proper k-coloring of $G$ can be seen as a separation of $G$ between k independent sets. We can then define our problem as finding the minimum number of independent sets such that each vertex
belong to at least one independent set and each independent set has a color compatible with the domains of its vertices. The number of variable is exponential but the linear relaxation is computed with column generation in [31].

We define the following problem ($\mathbf{P}_{\text{Stable}}$). $\Omega$ is the set of independent sets (whose size is exponential) of $G$ and $\Omega(c) \subseteq \Omega$ is the set of independent sets compatible with color $c$. More precisely, independent sets of $\Omega(c)$ are such that $\forall S \in \Omega(c), \forall v \in S, c \in \mathcal{L}(v)$. ($P_{\text{Stable}}$) is defined over the following boolean variables $\rho_{sc}$, the decision to use the s-th independent set of color $c$.

$$ (\mathbf{P}_{\text{Stable}}) \quad \text{minimize} \quad \sum_{c \in \mathcal{C}} \sum_{s \in \Omega(c)} \rho_{sc} \qquad (4.2a) $$

$$ \text{subject to} \quad \sum_{s|i \in V(s)} \sum_{c \in \mathcal{C}} \rho_{sc} \geq 1, \quad \forall i \in V, \qquad (4.2b) $$

$$ \sum_{s \in \Omega(c)} \rho_{sc} \leq 1, \quad \forall c \in \mathcal{C}, \qquad (4.2c) $$

$$ \rho_{sc} \in \{0, 1\}, \quad \forall s \in \Omega(c), \quad \forall c \in \mathcal{C} \qquad (4.2d) $$

The constraint (4.2b) implies that each vertex occurs in at least one selected independent set. In fact in the solution even if a vertex is contained into multiple selected independent set, choosing one of them does not change neither the optimal value nor the feasibility of the solution. Constraint (4.2c) implies that at most one independent set per color is selected in order to avoid the selection of multiple disjoints independent set of the same color (e.g a bipartite could be colored with two independent set of the same color without this constraint).

**k-Coloring formulation** Let ($\mathbf{P}_{\text{Col}}$) be the exponential formulation of the k-coloring problem. ($\mathbf{P}_{\text{Col}}$) is defined over the boolean variables $\rho_s$, the decision to use the s-th independent set of $\Omega$.

$$ (\mathbf{P}_{\text{Col}}) \quad \text{minimize} \quad \sum_{s \in \Omega} \rho_s \\ \text{subject to} \quad \sum_{s|i \in V(s)} \rho_s \geq 1, \quad \forall i \in V, \qquad (4.3) \\ \rho_s \geq 0, \quad \forall s \in \Omega $$

**Lemma 2.** ($\mathbf{P}_{\text{Col}}$) is an integer formulation for k-coloring when $G$ is chordal.

*Proof.* In order to prove it, we will use results on the maximum independent set problem on perfect graphs. Recall that chordal graphs are perfect graphs.

First, let's define the min/max polyhedral equality that will be used for this proof. Let $P_1$ and $P_2$ be two polyhedra and $x_1 \in P_1, x_2 \in P_2$. $P_1$ is equal to (i.e equivalent to) $P_2$ iff for any objective function $w$, $\max_{x_1 \in P_1} = \max_{x_2 \in P_2}$. To begin with, if $P_1 = P_2$, then it is evident that for any $w$, we have $\max_{x_1 \in P_1} = \max_{x_2 \in P_2}$. On the other hand, suppose that $\max_{x_1 \in P_1} = \max_{x_2 \in P_2}$ but $P_1 \neq P_2$. Then, it exists $x_0 \in P_1$ such that $x_0 \notin P_2$. Thus, it exists an hyperplane $c^t x = b$ (with $x \in P_1$) that separates the point $x_0$ from $P_2$, meaning that
$c^t x_0 > b$ and $c^t x < b, \forall x \in P_2$. That is, $\max_{x_2 \in P_2} c^t x_2 < \max_{x_1 \in P_1} c^t x_1$. Thus, two polyhedra are equals if and only if for all objective function, their maximum (resp. minimum) are equals.

Let $\text{Poly} := \text{conv}(x_s = \{0,1\}^{|V|})$ s an independent set) be the polyhedra of integral extreme points (solutions) of the maximum independent set problem. Let define the following linear programming formulation of the maximum independent set problem based on the *Cliques inequalities* along with its dual. Recall that $\mathcal{Q}$ is the set of maximal cliques of $G$.

$$ (\mathbf{P}_2) \quad \max \quad \sum_{i \in V} x_i \\ \sum_{i \in V(q)} x_i \le 1 \quad \forall q \in \mathcal{Q} \\ x_i \ge 0 \quad \forall i \in V \quad \left| \quad (\mathbf{D}_2) \quad \min \quad \sum_{q \in \mathcal{Q}} y_q \\ \sum_{q \in \mathcal{Q}|i \in V(q)} y_q \ge 1 \quad \forall i \in V \\ y_q \ge 0 \quad \forall q \in \mathcal{Q} \right. $$

The polyhedra of solution of $(\mathbf{P}_2)$ is defined as $\text{Poly}_2 := \{x|x \ge 0, x(q) \le 1 \text{ with } q \in \mathcal{Q}\}$. First, let show that $\text{Poly} = \text{Poly}_2$ (i.e the solutions of $(\mathbf{P}_2)$ are integral). From the definition of perfect graphs we have the following equivalent facts:

(i) $G$ is perfect

(ii) $\alpha(H) = \chi(\overline{H})$, for every induced sub-graph $H$ of $G$

(iii) For all induced sub-graph $H$ of $G$ and for all vertex $v$ of $H$, it exists a maximal clique $Q_v$ such that: $|Q_v \cap S| = 1$, for each maximal independent set of $H$.

(iv) For all induced sub-graph $H$ of $G$, it exists a maximal clique $Q$ such that: $|Q \cap S| = 1$, for each maximal independent set of $H$.

**Lemma 3 (Replication Lemma).** Suppose $G$ is perfect and let $v \in V$. Add $v'$ to $G$ and join it to each adjacent vertex of $v$ ($N(v) = N(v')$). The two vertices $v$ and $v'$ are not joined. Denote $G'$ the resulting graph, then, $G'$ is also perfect.

*Proof.* Firstly, we apply (iii) to $v$ and obtain that it exists $Q_v$ on $G$. Secondly, we check that (iv) holds for any induced sub-graph $H$ of $G$. If $H$ does not contains both $v$ and $v'$, then $H$ is isomorphic to a sub-graph of $G$, so (iv) holds for it. Otherwise, if $H$ contains both $v$ and $v'$, then $Q_v$ satisfies (iv) since a maximal independent set $S$ of $H$ either contains both $v$ and $v'$ or neither, but in such case, it is also a maximal independent set of $G$, so $|Q_v \cap S| = 1$. $\square$

By the replication lemma, we have $\max_{s \in S} w(s) = \min_{\sum_{y_q \ge w} y_q \ge 1} \sum_{q \in \mathcal{Q}} y_q \ge \min_{\sum_{y_q \ge w} y_q \le 1} \sum_{q \in \mathcal{Q}} y_q$. By duality, $\min_{\sum_{y_q \ge w} y_q \le 1} \sum_{q \in \mathcal{Q}} y_q = \max_{x(q) \le 1} w x$, but $\max_{s \in S} w(s) \le \max_{x(q) \le 1} w x$ so there is equality

and by the polyhedral equality, we have that $\text{Poly} = \text{Poly}_2$, thus, $(\mathbf{P}_2)$ is integral. $(\mathbf{P}_2)$ is dual integral on chordal graphs, meaning that $(\mathbf{D}_2)$ is an integral formulation of the cliques covering problem on chordal graphs<fnref n="1" />.

<footnote n="1">¹The proof is not reported here</footnote>
To conclude this proof, we will show that in perfect graphs, the solution polyhedra of ($\mathbf{D}_2$) is equal to the one of ($\mathbf{P}_{\text{Col}}$). Let $A_G = \{ \sum_{s \in S} \rho_s \ge 1 \forall i, \rho_s \ge 0 \forall s \in S \}$ be the solution polyhedra of ($\mathbf{P}_{\text{Col}}$) and $B_G = \{ \sum_{q \in Q} y_q \le 1 \forall i, y_q \ge 0 \forall q \in Q \}$ be the corresponding one for ($\mathbf{D}_2$). Then, we have by definition of the complementary of a graph (see section 2.2) that $A_G = B_{\bar{G}}$ and as $B_G$ is integral, $A_G$ is integral. Thus, ($\mathbf{P}_{\text{Col}}$) is an integral formulation for *k*-coloring when $G$ is perfect. $\square$
5

Lagrangian Relaxation

In (P<sub>Stable</sub>), the constraint (4.2b) can be relaxed in order to obtain the following La-
grangian sub-problem for any λ ≥ 0.

$$
(LAG) \quad \text{minimize} \quad w(\lambda) = \sum_{c \in \mathcal{C}} \sum_{s \in \Omega(c)} \rho_{sc} + \sum_{i \in V} \lambda_i \left(1 - \sum_{s \mid i \in V(s)} \sum_{c \in \mathcal{C}} \rho_{sc}\right) \quad (5.1a)
$$

$$
\text{subject to} \quad \sum_{s \in \Omega(c)} \rho_{sc} \le 1, \quad \forall c \in C, \qquad (5.1\text{b})
$$

$$
\rho_{sc} \in \{0,1\}, \quad \forall s \in \Omega(c), \quad G \tag{5.1c}
$$

**A max weighted independent set per color.** Let $G_c$ be the induced sub-graph of $G$
where all vertices have the color $c$ in their domains. Observe in (LAG) that no constraints
are affecting multiples colors at the same time. Thus, each color leads to an independent
sub-problem. Moreover, the objective function can be refactored and written:

$$
\text{minimize} \quad w(\lambda) = \sum_{c \in \mathcal{C}} \sum_{s \in \Omega(c)} \left(1 - \sum_{i \in V(s)} \lambda_i\right) \rho_{sc} + \sum_{i \in V} \lambda_i \quad (5.2a)
$$

Since $\sum_{i \in V} \lambda_i$ is constant, for each color the objective function can be stated as: $\min \sum_{s \in \Omega(c)} (1 - \sum_{i \in V(s)} \lambda_i) \rho_{sc}$. By definition, $s$ is an independent set of $G_c$. From constraint (5.1b) we have at most one *independent* set per color. Thus, for each color the sub-problem is to find an independent set $s$ minimizing $(1 - \sum_{i \in V(s)} \lambda_i)$ which is equivalent to maximize

$$
\sum_{i \in V(s)} \lambda_i, \text{ i.e to find a maximum weighted independent set over the graph } G_c.
$$

The optimal value of (LAG) can be obtained by computing the solution of each sub-
problem. For the *maximum weighted independent set* (MWIS) problem an *IP* model
could be as follow:

$$
\text{maximize} \quad \sum_{i \in V(G_c)} \lambda_i x_i \tag{5.3a}
$$

$$
\text{subject to} \quad x_i + x_j \le 1, \quad \forall v_i v_j \in E(G_c), \qquad (5.3\text{b})
$$

$$
x_i \in \{0,1\}, \quad \forall i \in V(G_c) \tag{5.3c}
$$

Let $s^*$ be an optimal (i.e maximum weighted) *independent set* of $G_c$ and $z^*$ its value. If $z^* > 1$, then $s^*$ is added to $S^-$, the set of weighted independent sets that minimize $w^*(\lambda)$
(i.e such that $(1 - \sum_{i \in V(s^*)} \lambda_i) < 0$). The optimal value $w^*(\lambda)$ of (LAG) is given by setting all corresponding $\rho_{s^*c}$ to 1 i.e

$$w^*(\lambda) = \sum_{s^* \in S^-} \sum_{c \in \mathcal{C}} (1 - \sum_{i \in V(s^*)} \lambda_i) + \sum_{i \in V} \lambda_i$$

Thus, $w^*(\lambda)$ can be obtained by solving a maximum weighted independent set problem for each color.

**Marginal Cost and Filtering.** Consider for a color c, $S_{x_i=1}^*$ an optimal solution of the MWIS problem on $G_c$ that contains vertex $v_i$ and $z_{x_i=1}^*$ its value. The marginal cost of $x_i$ is defined as $z_{x_i=1}^* - z^*$ i.e $\sum_{j \in S_{x_i=1}^*} \lambda_j - \sum_{j \in S^*} \lambda_j$.

The marginal cost of assigning a color to a vertex $v_i$ can be computed directly from the marginal cost of $x_i$ in the MWIS problem on $G_c$ when $G_c$ is a chordal graph. Let $w_{S_{x_i=1}^*}^*$ be the value of an optimal solution of (LAG) such that $v_i$ is assigned to color c'. Then, $w_{S_{x_i=1}^*}^* = \sum_{s^* \in S^-} \sum_{c \in \mathcal{C} \setminus \{c'\}} (1 - \sum_{i \in V(s^*)} \lambda_i) + \sum_{i \in V} \lambda_i + (1 - \sum_{j \in S_{x_i=1}^*} w_j)$. Observe that for each vertex, its marginal cost is at most 1.

Recall that, as (LAG) is a relaxation of ($\mathbf{P}_{\text{Stable}}$), for any $\lambda \ge 0$ we have: $\min w(\lambda) \le \text{Opt}((\mathbf{P}_{\text{Stable}}))$. Let $\bar{z}$ be an upper bound of the optimal value of ($\mathbf{P}_{\text{Stable}}$) given by one feasible solution. If $w_{S_{x_i=1}^*|S^* \in \Omega(c')}^* > \bar{z}$, it means that for any feasible solution of ($\mathbf{P}_{\text{Stable}}$) where the vertex $v_i$ is assigned to the color $c'$, its value will be greater than $\bar{z}$. Thus, $c'$ could be removed from the possible values (i.e domain) of the vertex $v_i$.

In order to efficiently solve the Lagrangian sub-problem, we will consider the restricted case where $G$ is chordal.
# Filtering: Chordal Case

We will consider in this section the case where $G$ is *chordal*, a condition where *list-coloring* is still *NP-Hard*. As $G$ is chordal, the restriction $G_c$ of $G$ for each color $c$ is also chordal. In [1], Frank proposed a *polynomial algorithm*<fnref n="1" /> for the *maximum weighted independent set* problem in chordal graphs. The Lagrangian sub-problem presented in Section 5 is therefore polynomial. We can hope for an efficient resolution of the *Lagrangian dual* by bounding the number of iterations of the *subgradient algorithm*. The algorithm given in [1] is based on the *perfect eliminating order* of the graph (see Section 2.2).

## 6.1 Frank Algorithm

Assume without loss of generalisation that $G$ is a chordal graph with a *peo* $O = \{v_1, \dots, v_n\}$ such that $\forall v_i$, the sub-graph induced by $N(v_i) \cap \{v_{i+1}, \dots, v_n\}$ is a clique. Let $w_i'$ be the current weight of vertex $v_i$ during the algorithm execution with a starting value equals to $w_i$.

**Forward phase.** The algorithm iterates over the vertices in the order of the peo and stops at the first vertex $v_i$ with $w_i'$ strictly positive and mark $v_i$ **as red**. For each vertex $v_j$ such that $j > i$ and $v_iv_j \in E$ remove $w_i'$ from $w_j'$. At any time if $w_j'$ becomes negative, it can be set to 0. Let $R$ be the set of red marked vertices obtained at the end of the algorithm. Moreover, we will denote $Q_R$ the set of the corresponding cliques in the *perfect eliminating order* i.e $Q_R = \{N(v_i) \cap \{v_{i+1}, \dots, v_n\} | v_i \in R\}$. Keep in mind that each clique is related to a vertex $v_i$ at position $i$ in the peo and weight $w_i'$ at the end of Frank's algorithm.

**Backward phase.** Then, go through all red marked vertices in the reverse order and mark blue each vertex that is not adjacent to an already blue marked vertex. Let $U$ be the independent set of blue marked vertices obtained after this phase.

**Example.** Take for example the graph $G$ and its corresponding weights given in figure 6.1. It can be checked that $\{A, B, G, H, C, D, F, E\}$ is a valid *peo* of $G$. Consider the first iteration where $v_i = A$. As $w_A' = 9 > 0$, we mark $A$ in red and for each adjacent

<footnote n="1">¹Algorithm is written in appendix, see algorithm 2.</footnote>
<figure><img src="image_15.png" /><figcaption>Figure 6.1: Frank algorithm for MWIS on example 2.3</figcaption></figure>

vertex of A among {$B, \dots, E$} we remove $w'_A$. So $w'_B$ and $w'_C$ become respectively 0 and 1. At the next iteration, B is skipped and G is marked red. The corresponding *clique* is {$G, H, F$} so $w'_H$ becomes 0 and $w'_F$ becomes 1. Once all vertices of G have been considered, we have $R = \{A, G, C, D\}$. We go through R in the reverse order and select first D. As C is adjacent to D, it is not considered. Then, G and A are selected. We obtain $U = \{D, G, A\}$.

**Optimality of the example.** In example 6.1, $U$ is a feasible solution of the maximum weighted independent set problem with $z = 27$. We can observe that $Q_R$ is a set of weighted clique such that for each vertex $v_i$, the sum of the weights of cliques in which it is contained is at least $w_i$. For example, $C$ is in $\{A, B, C\}$ and $\{C, D, E\}$, $w_C = 10$ and $\{A, B, C\} \times 9 + \{C, D, E\} \times 1 = 10$. Also, the sum of weights of all cliques in $R$ is 27. In this example, $Q_R$ is a feasible solution for the dual problem of MWIS with the same value as $z$. Thus, the algorithm is optimal on example 6.1.

Let's denote $N_R(v_i)$, the red neighborhood of vertex $v_i$ (vertices marked red adjacent to $v_i$) and $N_R^-(v_i) = N_R(v_i) \cap \{v_1, \dots, v_{i-1}\}$ the red neighborhood of $v_i$ before $i$ in the peo. On the example $N_R(B) = \{A, C\}$ and $N_R^-(B) = \{A\}$.

**Theorem 2 (Optimality of Frank's algorithm).** Frank's algorithm computes a maximum weighted independent set.

*Proof.* Consider the following primal and dual formulations (respectively $P_I$ and $D_I$) of
the maximum independent set problem with $\mathcal{Q}$ is the set of maximal cliques of $G$:

$$ (\mathbf{P}_I) \qquad \text{maximize} \quad z = \sum_{i \in V} w_i x_i \qquad (6.1a) $$

$$ \text{subject to} \quad \sum_{i \in V(q)} x_i \le 1 \quad , \quad \forall q \in \mathcal{Q}, \qquad (6.1b) $$

$$ x_i \in \{0, 1\}, \quad \forall i \in V \qquad (6.1c) $$

$$ (\mathbf{D}_I) \qquad \text{minimize} \quad w = \sum_{q \in \mathcal{Q}} y_q \qquad (6.2a) $$

$$ \text{subject to} \quad \sum_{q \in \mathcal{Q} | i \in V(q)} y_q \ge w_i, \quad \forall i \in V, \qquad (6.2b) $$

$$ y_q \ge 0, \quad \forall q \in \mathcal{Q} \qquad (6.2c) $$

Optimality of Frank's algorithm relies on strong linear duality. The algorithm terminates with a feasible solution of $(P_I)$ (an independent set referred as $U \subseteq V$) as well as a feasible solution of $(D_I)$ (a system of weighted cliques referred as $\mathcal{Q}_R$) of same cost (see the example of Figure 6.1).

* During the backward phase two vertices marked blue can not be adjacent by construction. Thus, $U$ is an *independent set* of $G$ and is primal feasible.

* At the end of the forward phase, the cliques of $\mathcal{Q}_R$ containing a vertex $v_i$ sums to a total weight greater than $w_i$. Indeed, each $w'_i$ drops to zero (or below) during the execution. Therefore, $R$ is dual feasible.

* It remains to show that $z(U) = w(\mathcal{Q}_R)$. We have $z(U) = \sum_{i \in U} w_i$ and $w(\mathcal{Q}_R) = \sum_{q \in \mathcal{Q}_R} y_q = \sum_{i \in R} w'_i$. Firstly, note that the weight $w_i$ of a vertex $i \in U$ is spread among its final weight $w'_i$ and the final weights of the red cliques it belongs to. More precisely $w_i = \sum_{j \in N_R^-(v_i)} w'_j + w'_i$. So

$$ \sum_{i \in U} w_i = \sum_{i \in U} \left( \sum_{j \in N_R^-(v_i)} w'_j + w'_i \right) \qquad (6.3) $$

Secondly, note that for any two vertices $i$ and $k$ of $U$, we have $N^-(v_i) \cap N^-(v_k) = \emptyset$.

Indeed, if they had a common vertex in past neighborhoods, by definition of a peo, $i$ and $k$ would be in a clique together. Thus, it holds that $N_R^-(v_i) \cap N_R^-(v_k) = \emptyset$.

Therefore, equality (6.3) can be expanded to $\sum_{i \in U} w_i = \sum_{j \in R \setminus U} w'_j + \sum_{i \in U} w'_i = \sum_{j \in R} w'_j$.

Thus, we have $z(U) = \sum_{i \in U} w_i = \sum_{j \in R} w'_j = w(\mathcal{Q}_R)$ and the two solutions have the same cost (i.e $z(U) = w(\mathcal{Q}_R)$) which proves their optimality.

By the *strong duality* theorem, Frank's algorithm is optimal. $\square$
**Complexity.** The time complexity of finding a peo of a chordal graph is $O(m+n)$ [14]. The forward and backward phase runs in $O(m)$. We can also analyse the complexity based on the cardinality $\omega$ of a maximum clique which be useful later on. In this case, Frank's algorithm runs in $O(\omega n)$.

**Naive filtering.** Once $z^*$ has been computed, the marginal cost of each vertex $v$ can be computed by enforcing $v$ to be in the solution and calling Frank's algorithm for the restricted problem. For each vertex $v_i$, Frank algorithm can be called on $V \setminus N(v_i)$ (keep the same peo but skip vertices of $N(v_i)$) and computes an optimal solution that contains $v_i$ of value $z^*_{v_i}$. The marginal cost of $v_i$ is $z^*_{v_i} - z^*$. Assuming the peo is built only once, the complexity of the naive filtering approach is in $O(nm)$ or, when expressed with $\omega$: $O(\omega n^2)$.

## Reduced Cost and Filtering

The reduced cost of variable $x_i$ is denoted $\overline{rc}(x_i)$ and can be computed from a dual solution (e.g $y^*$):

$$ \overline{rc}(x_i) = w_i - \sum_{q \in \mathbb{Q} | i \in V(q)} y_q^* $$

We observe that reduced costs are readily available from Frank's algorithm. A negative weight $w'_i$ is set to zero in the original paper of Frank for sake of clarity. But reduced costs are available if we maintain weights completely and let them take negative values. The final value of $w'_i$ corresponds to the reduced cost of vertex $i$ in the dual solution given by the cliques so that $w'_i = \overline{rc}(v_i)$ in the dual solution produced when the algorithm terminates. The algorithm works with any peo of $G$. However, even if the solutions for $(P_I)$ and $(D_I)$ are optimal, there is no guaranty that for a given vertex, its resulting reduced cost corresponds to its marginal cost.

**Example.** In the example of Figure 6.1, since $A$, $G$ and $D$ are in an optimal solution, their exact reduced cost is 0. In green, reduced cost of $B$, $H$, $F$ and $E$ are exact. However, with this peo, the reduced cost of $C$ appears to be 0. But $z^*_{x_{C=1}} = 20$ (with $U = \{C, F\}$) and the marginal cost (i.e exact reduced cost) of $C$ is 27-20=7. Note also that for a given peo, the reduced costs of red marked vertices will be 0. A single dual solution is therefore not enough to know all exact reduced costs.

**Observation 3.** Formulation $(P_I)$ is integral when $G$ is chordal.

*Proof.* The proof comes directly from the optimality proof of Frank's algorithm since it builds an integer primal and dual solution (resp. to $(P_I)$ and $(D_I)$) of same cost. Thus, on chordal graphs, $(P_I)$ is integral. □

Since $(P_I)$ is integral, we know that there always exists a dual solution providing the exact reduced cost of a vertex [15]. We can observe that Frank's dual solution provides the exact reduced costs of the vertices after the last red vertex at the end of the execution. Typically reduced costs of vertices E and F in example of Figure 6.1 (resp. -7 and -8) are guaranteed to be exact.
**Observation 4.** For all vertex $v_j$, after an iteration of Frank's algorithm, it holds that
$\forall v_k \in N_R^-(v_j)$, $N^+(v_k) \subseteq N(v_j) \cap \{v_j\}$.

*Proof.* The proof comes directly from the definition of a *perfect eliminating ordering*. As $v_j$ is a predecessor of $v_k$, it must belongs to a clique with each other adjacent predecessor of $v_k$. $\square$

**Example.** Consider vertex $F$ in the example of Figure 6.1. $N_R^-(F) = \{G, H, D\}$ and for each, it holds that $N^+(v_k) \subseteq N(v_j) \cap \{v_j\}$. Respectively $N^+(G) = \{H, F\}$, $N^+(H) = \{F\}$ and $N^+(D) = \{F, E\}$.

**Lemma 4 (Marginal cost of vertices after the last red).** For a given peo, after an execution of Frank's algorithm, it holds that for all vertex $v_j$ after the last red vertex: 
$$z_{|v_j}^* = \sum_{i \in R \setminus N_R(v_j)} w_i' + w_j.$$

*Proof.* First, observe that as $v_j$ is after the last red vertex, $N_R^-(v_j) = N_R(v_j)$. Moreover, from observation 4, we can see that for each vertex $v_k \in N_R(v_j)$, $w_k'$ will be removed only on vertices that are adjacent of $v_j$ (i.e $v_k$ affects only vertices that belong to the neighborhood of $v_j$). Then, by keeping the same peo and removing all adjacent vertices of $v_j$, other vertices will have the exact same value after a new execution of Frank's algorithm. In other words, based on the same peo, an execution of Frank on $V \setminus N(v_j)$ would give the exact same $w_i'$ for vertices of $V \setminus N(v_j)$. Also, as all adjacent vertices are no longer considered, the value of $v_j$ won't be changed. Thus, the value of the solution will be equal to the sum of the final weights of red vertices that are not adjacent to $v_j$ plus the original value of $v_j$. $\square$

**Example.** Consider again the vertex $F$ in example 6.1 with $N(F) = \{G, H, D, E\}$. Figure 6.2 compare the execution of Frank's algorithm with and without the neighborhood of $F$. Firstly, observe that $w'_A$, $w'_B$ and $w'_C$ (the values of vertices not connected to $F$) are not affected by the removal of $N(F)$. Secondly, $z_{|F}^* = 20$ and it can be seen that $z_{|F}^* = w'_A + w'_C + w'_F$. Finally, the value of $F$ is not modified, we have $w'_F = w_F$ and thus, in this example $z_{|v_j}^* = \sum_{i \in R \setminus N_R(v_j)} w_i' + w_j$ holds.

<figure><img src="image_16.png" /><figcaption>Figure 6.2: Example the executions of Frank's algorithm for the example of Figure 6.1 with and without $N(F)$ considered.</figcaption></figure>

**Theorem 5 (Exact reduced costs).** Consider a chordal graph $G$ and an execution of Frank's algorithm over a given peo. Reduced cost of all vertices after the last red vertex in the peo are exact.
*Proof.* Let $v_j$ be such a vertex after the last red and let's show that it's reduced cost $w'_j$ is exact i.e that an optimal solution including vertex $v_j$ has a cost $z^* + w'_j$. Consider the primal and dual formulations restricted with the additional constraint $x_j = 1$ respectively denoted ($\mathbf{P}_{\mathcal{I}|x_j=1}$) and ($\mathbf{D}_{\mathcal{I}|x_j=1}$) (the dual ($\mathbf{D}_{\mathcal{I}|x_j=1}$) in particular is shown below). To prove that $w'_j$ is the exact reduced cost of $v_j$, we build two feasible dual and primal solutions of the two restricted formulations with the same cost $z^* + w'_j$. Keep in mind that $z^* = w^*$ (resp. with $x^*$ and $y^*$) is the optimal value (resp. solutions) of the original unrestricted ($\mathbf{P}_{\mathcal{I}}$) and ($\mathbf{D}_{\mathcal{I}}$).

The dual solution for ($\mathbf{D}_{\mathcal{I}|x_j=1}$) is referred to as ($\tilde{y}, \tilde{\beta}_j$) and we simply set $\tilde{\beta}_j = w'_j$ and $\tilde{y} = y^*$. ($\tilde{y}, \tilde{\beta}_j$) is dual feasible for ($\mathbf{D}_{\mathcal{I}|x_j=1}$) since $\tilde{\beta}_j$ is set to the gap (in $y^*$) of the dual constraint of vertex $v_j$. Its cost is $w^* + w'_j = z^* + w'_j$ and the dual constraint is tight (by construction) so that $w'_j = \tilde{\beta}_j = w_j - \sum_{q \in \mathcal{Q} | j \in V(q)} \tilde{y}_q$.

$$ (\mathbf{D}_{\mathcal{I}|x_j=1}) \quad \begin{array}{ll} \text{minimize} & \displaystyle \sum_{q \in \mathcal{Q}} y_q + \beta_j \\ \text{subject to} & \displaystyle \sum_{q \in \mathcal{Q} | i \in V(q)} y_q \ge w_i, \quad \forall i \in V \setminus \{j\}, \\ & \displaystyle \sum_{q \in \mathcal{Q} | j \in V(q)} y_q + \beta_j \ge w_j, \\ & y_q \ge 0, \quad \forall q \in \mathcal{Q}, \\ & \beta_j \in \mathbb{R} \end{array} \qquad (6.4) $$

The primal solution for ($P_{\mathcal{I}|x_j=1}$) is denoted $U'$.

* Build $U'' \subseteq R \setminus N_R(v_j)$ by applying the backward step of Franck on the red vertices defined as $R \setminus N_R(v_j)$ and set $U' = U'' \cup \{v_j\}$. $U'$ is a valid independent set including $v_j$ by construction i.e a feasible solution of ($P_{\mathcal{I}|x_j=1}$).

* From lemma 4, we have

$$ z(U') = z(U'') + w_j = \sum_{i \in R \setminus N_R(v_j)} w_i' + w_j $$

Then, $z(U') = \sum_{i \in R \setminus N_R(v_j)} w_i' + (\sum_{q \in \mathcal{Q} | j \in V(q)} \tilde{y}_q + \tilde{\beta}_j) = \sum_{i \in R \setminus N_R(v_j)} w_i' + \sum_{i \in N_R(v_j)} w_i' + w_j' = \sum_{i \in R} w_i' + w_j' = z^* + w_j'$. Finally $z(U') = w^* + w_j'$, by strong duality ($z^* = w^*$) and $U'$ is optimal.

Since $U'$ is an optimal solution of ($P_{\mathcal{I}|x_j=1}$) of value $z^* + w_j'$, $w_j'$ is the marginal cost of $v_j$. $\square$

It turns out that exact reduced costs of additional vertices (other than the ones after the last red) can be computed and the criterion of Theorem 5 can be generalized. More precisely, it is valid when only independent neighborhoods ends the peo.

**Observation 6.** In one iteration of Frank algorithm, the reduced cost of a vertex $v_i$ whose red neighborhood occurs before position $i$ in the perfect eliminating order (i.e $N_R(v_i) \cap \{v_{i+1}, \dots, v_n\} = \emptyset$) is exact.
Theorem 5 suggests that we can obtain the exact reduced cost of all vertices using a family of *peo* where each vertex appears in the last clique of at least one *peo*. Such an algorithm would therefore be able to enforce arc-consistency. Let's show that such a family exists.

**Observation 7.** *Given a chordal graph G, for any clique *q* of G, there exists a *peo* that ends with the vertices of *q*.*

*Proof.* It is known that every chordal graph G which is not a clique contains at least two non-adjacent simplicial vertices [14]. A given clique can therefore always be postponed at the very end. During the process, when a simplicial vertex must be selected, either the resulting induced graph is *q* or it exists $v \notin q$ which is a simplicial vertex and can be selected first. □

Note that the vertices of the last clique must appear in the proper order to ensure
that the first vertex is a red one. This would ensure, by theorem 5 that all reduced costs
are exact for the last clique.

**Theorem 8 (Complexity of arc-consistency with reduced of cost).** *Arc-consistency can be achieved in O(|Q|m).*

*Proof.* From observation 7, for each clique $q \in Q$, we can create a *peo* such that all vertices of *q* are at the end. Since all vertices of *q* are at the end of the *peo*, they can be computed in any order. During the execution, once all vertices but the one of *q* have been considered, mark red the vertex $v_i$ defined as $\max_{i \in q} w_i'$ and compute the resulting weights of the others. From Theorem 5, for each vertex of *q*, we obtain its *marginal cost*. Each vertex of *V* appears in at least one clique of *Q*. By executing the algorithm once for each $q \in Q$ with such *peo*, we obtain the marginal cost of each vertex of *G* in $O(|Q|m)$. Since *G* is chordal, $|Q| \le n$. □

**Example.** In example 6.1, we have that $\overline{rc}(B)$, $\overline{rc}(H)$ $\overline{rc}(F)$ and $\overline{rc}(E)$ are their respective exact reduced cost. Observe that $H, F$ and $E$ are last among their red-marked neighbours. However, there is no guaranty for $B$, and the reduced cost of $C$ is 0. With the *peo* {$G, H, F, D, E, A, C, B$} we obtain the execution (**b**) shown in Figure 6.3 where $\overline{rc}(C) = -7$. In such execution, $\overline{rc}(C)$ and $\overline{rc}(B)$ are guaranteed to be exact. From these two *peo* we obtain all the *marginal costs* of the vertices of *G*.
<figure><img src="image_17.png" /><figcaption>Figure 6.3: Example of two executions of Frank's algorithm for the example of Figure 6.1 providing together the exact reduced costs of all vertices. The reduced costs of vertices F,E,C,B are known to be exact by Theorem 4. The reduced costs of vertex H is known exact due to observation 5.</figcaption></figure>

## 6.2 Clique Tree Decomposition

Appendix A.1 proposes an alternative way to Frank's algorithm for solving the maximum weighted independent set in a chordal graph and compute the exact reduced cost of each vertex. This algorithm is based on dynamic programming, taking advantage of a clique-tree decomposition of the chordal graph. Its complexity is in $O(n\omega^2)$ which is higher than the $O(n\omega)$ of Frank. However, it provides the exact reduced costs of each vertex as a by-product (for free after solving) leading to an arc-consistency algorithm of the same complexity $O(n\omega^2)$. As a result, it is incomparable to the $O(|Q|m)$ based on reduced costs presented section 6.1. But more importantly, it potentially generalizes beyond chordal graphs.

This algorithm is described in appendix since it was established by my supervisor, independently, of the present internship.

## 6.3 Perfect Graphs Extension

A first step to generalize beyond chordal graphs would be to generalize to perfect graphs. Recall that a graph $G$ is called perfect *iff* $\chi(G) = \omega(G)$. It exists an algorithm for the *maximum weighted independent set* problem which solve it in polynomial time and space on these graphs [22]. Such algorithm use the ellipsoid method [23] in order to obtain $w^*$ (the value of the *maximum weighted independent set*) of a graph in polynomial time. This method is called one time for each vertex $v$ on $G_v = (V\setminus\{v\}, E)$. Let $w_v^*$ be the value of the *maximum weighted independent set* of $G_v$. For each vertex, either $w_v^* = w^*$ in which case it means that it exists an *independent set* of maximum value in $G$ that does not contain $v$. Otherwise, if $w_v^* < w^*$, it means that $v$ belongs to the *maximum independent set*.

Let $t$ be the complexity of the ellipsoid method used to compute $w^*$ for a perfect graph (which is polynomial). The algorithm depicted in [22] runs in $O(nt)$. For each vertex $v$, we can set $w'_u = 0$ for each vertex $u$ adjacent to it ($u \in N(v)$). Then by running
the ellipsoid method with $G$ and $w'$, we obtain the value of the *maximum independent set* of $G$ such that $v$ belongs to it (if $w_v < 0$, then we need to add $w_v$). From this, we can compute the marginal cost of each vertex of $G$ with the same complexity of this algorithm.
<figure><img src="image_18.png" /></figure>
— 7 —

Filtering Algorithm for COLORING

The filtering algorithm of COLORING($\mathcal{X}$, $y$, $G$) is shown in Figure 7.1. At first, $\lambda$ is param- eterized depending on $G$ characteristics (e.g $n$, $m$, ...) and the *sub-gradient* algorithm chosen (e.g *Geometric* or *Newton*). In practice, a *maximum number of iteration T* and a *maximum solving time* are also set.

**Iteration t.** The *Lagrangian* resolution process create for each color $c$ the corresponding sub-graph $G_c$ and solve a *maximum weighted independent set* problem on $G_c$ with the current $\lambda$ values ($w_i = \lambda_i, \forall i \in V$). Then, $\underline{y}$ is updated with the value $w^*(\lambda)$ (see Section 5). If $\underline{y} > \bar{y}$, the process fail, with the current state of $G$, $\bar{y}$ is the best feasible upper bound for $\chi(G, \mathcal{L})$. Otherwise, if the *marginal costs* of $x_i$ can be efficiently computed in the *MWIS* problem, filtering over the domains of $\mathcal{X}$ can be applied. Such filtering is activated only if $\bar{y} - \underline{y} \le 1$ (see Section 6). Then, $\lambda$ is updated with the corresponding step $\mu_t$ defined by the *sub-gradient algorithm* (see Section 2.4).

<figure><img src="image_19.png" /><figcaption>Figure 7.1: Lagrangian Filtering Process</figcaption></figure>

**Branch and Bound.** During the branch and bound phase, the filtering of COLORING is computed at each node. Thus, whenever the solver makes a decision (e.g assigning a color to a vertex), $G$ and domains of $\mathcal{X}$ are updated, then the *Lagrangian Sub-Problem*
process is called for *T* iterations. At each node, previous $\lambda$ is kept in order to restart from the last best *Lagrangian* multiplier.

**Zykov Branching.** The extended constraint COLORING($\mathcal{X}, \mathcal{E}, y, G$) reacts to Zykov decomposition branching method (see Section 3.2). If such a method is used, during the branch and bound process, $G$ is updated (e.g an edge is created) and the *Lagrangian* sub-problem is computed with the resulting $G$. With a *color-assignment* method, the modifications appears only for the resolution of *MWIS* of the corresponding $G_c$. In contrast, with the *Zykov's recurrence*, since the decision is made on $G$, it can modify multiple sub-graphs $G_c$ at the same time. Observe also that, since $G$ is modified, the *maximum weighted independent set* problem can become polynomial (e.g if $G$ becomes chordal).

**Example.** It can be observed in example 3.3 that $G$ becomes *chordal* under the decision $G/(AD)$. In such case, in the *MWIS* sub-problems, *marginal costs* can be computed efficiently and filtering can occur on domains of $\mathcal{X}$.

**Implementation.** A preliminary version of the constraint COLORING has been implemented on the solver *ChocoSolver* [34] along with its *Lagrangian* resolution process. For the moment, filtering algorithms (Section 6) have only been developed in the chordal case. Thus, for the moment COLORING is only functional for chordal graphs. In the next section, we will consider its use within a *constraint programming* model and provide a method to solve the *list-coloring* problem on chordal graphs.
List-Coloring Complete Resolution Process

Recall that for $G = (V, E)$, $\mathcal{Q}$ is the set of its maximal cliques. Consider the following constraint programming model :

**Complete Model (COL):**

$$x_i \neq x_j, \qquad \forall (ij) \in E \quad (8.1)$$

$$\text{ALLDIFFERENT}([x_i | i \in q]) \qquad \forall q \in \mathcal{Q} \quad (8.2)$$

$$\text{ATMOSTNVALUES}([x_1, \dots, x_n], y) \qquad (8.3)$$

$$\text{COLORING}([x_1, \dots, x_n], y, G) \qquad (8.4)$$

$$x_i \in D(x_i), \qquad \forall i = 1, \dots, n \quad (8.5)$$

$$y \in \mathbb{N} \qquad (8.6)$$

The same way as for (DEC) (see Section 3, a support for model (COL) (i.e an assignment that respect all constraints, see Section 2.1) is a valid solution for the list-coloring problem on $(G, \mathcal{L})$. However, the difference lies in the level of reasoning. First, in (DEC) $y$ is given only by constraint ATMOSTNVALUES whereas in (COL), it is also filtered by COLORING. Furthermore, reasoning of constraints $x_i \neq x_j$ is very limited and filtering only occurs during the branch and bound process when values are assigned. In (COL), constraints (8.2) withdraw values right from the root node.

**Uses Example.** Consider the *timetabling* problem *Honours and Subjects* defined in Section 3.3. Recall that it corresponds to finding the minimum number of time slots needed to schedule a list of lessons with respect to certain constraints. A graph $G = (V, E)$ is built with a vertex $v_i$ for each lesson $i$ and an edge between each pair of lessons that cannot occurs at the same time (e.g lessons $i$ and $j$ have students in common). In such example, a variable $x_i \in \mathcal{X}$ is defined for each lesson with $D(x_i)$ its set of available time slots. $\bar{y}$ is set to the maximum number of time slots available. Then, $(COL(\mathcal{X}, y))$ gives a solution to the *Honours and Subjects* problem.

**Exact Resolution for Chordal Graphs.** Let (LAG) be the solver computing the optimal value of the *Lagrangian* sub-problem and (MIP) be an *Integer Programming* solver. Recall the problem ($\mathbf{P}_{\text{Stable}}$) define in Section 4.1 with the optimal value $z^*$ and the constraint programming model (COL).
**Algorithm 1** *list-coloring* Resolution Algorithm for Chordal Graphs

**Require:** $G = (V, E)$ a chordal graph, a list $\mathcal{L}_i \subset \mathbb{N}$, of available colors for each vertex

**Return:** $y = [\chi(G, \mathcal{L}), \bar{\chi}(G, \mathcal{L})]$

$\mathcal{D}(x_i) \leftarrow \mathcal{L}_i, \forall i \in V$

$\mathcal{D}(y) \leftarrow \{c | c \in \bigcup_i \mathcal{L}_i\}$

**Solve (LAG) on (G, L):**

$S \leftarrow$ The set of maximal Independent sets obtained by the MWIS solver.

$\bar{y} \leftarrow w^*(\lambda)$

**Solve ($\mathbf{P}_{\text{Stable}}(S)$):**

$\bar{y} \leftarrow z^*$

if $\bar{y} = \bar{y}$ then return $[y, y]$

▷ We have proof of optimality, $y = \chi(G, \mathcal{L})$

else Solve (*COL*) with the upper bound $\bar{y} - 1$ and the last $\lambda$ obtained:

if (*COL*) fails then return $[\underline{y}, \bar{y}]$

▷ (*COL*) proved optimality of $\bar{y}$

else return $[\underline{y}, \bar{y}]$, $\bar{y}$' the solution of (*COL*)

▷ (*COL*) has closed the gap

end if

end if

Algorithm 1 defines a process to solve *list-coloring* on chordal graphs using *constraint programming* to prove optimality of the solution. First, $\underline{y}$, a lower bound of $\chi(G, \mathcal{L})$ is calculated using the *Lagrangian relaxation*. The *Lagrangian relaxation* also gives a set of *stable* for each color obtained from the *Maximum Weigthed independent set* resolution. The problem $(\mathbf{P}_{\text{Stable}})$ can then be solved using those sets as $\Omega(c)$. Then, $(\mathbf{P}_{\text{Stable}})$ gives an upper-bound $\bar{y}$ on $\chi(G, \mathcal{L})$. In case where $\underline{y} = \bar{y}$, we obtain $y = \chi(G, \mathcal{L})$, the algorithm stop with an optimal solution. On the other hand if there is a gap between $\underline{y}$ and $\bar{y}$, the model (*COL*) is used to prove by contradiction over the domains that $\bar{y}$ is optimal. If no contradiction is raised, the *branch and bound* solving process can be use to return a better solution.
# Benchmarks and Experimental Results

During this internship, implementations have been made in Java. The *Lagrangian resolution* process have been implemented along with the Frank's algorithm for *maximum weighted independent set*. A preliminary version of COLORING for *ChocoSolver* has also been implemented. In order to validate them, it has been tested on various benchmarks. Our evaluations have been made on a computer with 2.60GHZ Intel Core i7-6700HQ CPU and 8 Go of ram. Solvers used are *ChocoSolver* version 4.10.14 and IBM ILOG CPLEX version 22.1.1.

## 9.1 Benchmarks

At first, our benchmarks were based on *DIMACS* instances used in [25] for the *k-coloring* problem. Since we focused on the restricted case of chordal graphs, a preliminary benchmark has been developed using either chordal graphs built from scratch or *DIMACS* instances modified to be chordal (i.e with added edges). In parallel, *lists* were created with *n* colors and randomly generated holes in it.

Later on, two benchmarks have been developed. The first one (refereed as *Caner*) is based on randomly generated chordal graphs with distinct characteristics [37]. The second (refereed as *k-Tree*) has been created from scratch by my supervisor with the objective to create hard instances for the model (P) on *CPLEX* solver. A *k-Tree* is a chordal graph where each *maximal* clique is of size *k+1*. In order to avoid cases where *hardness* of the problem comes only from the graph structure, *lists* have also been created in order to obtain difficult instances of the *Hitting Set* problems. Sizes of the instances go from *n* = [50, 100, 150] (small instances) to *n* = 500 (large instances). Sizes of the *lists* are the same for all vertices and based on a percentage of *n* ([6, 14, 20, 26, 30, 33]). A limit of 600 seconds was set for the *CPLEX* solver and 60 seconds for the *Lagrangian* resolution process.

## 9.2 Results

**Arc-consistency of MWIS.** Frank's algorithm explained in Section 6 have been implemented. Based on Observation 7 an algorithm for chordal graphs creating a *perfect eliminating order* ending with a fixed clique have been developed. Based on the *Caner* benchmark, a comparison of the filtering of *maximum weighted independent set* problem
on chordal graphs has been conducted. For each graph, random weights are generated (within a range [0, 100]) and three different filtering are applied. Firstly, the naive implementation in $O(nm)$ which obtains arc-consistency and serves as baseline. Secondly, using only one peo we obtain the filtering after one iteration of Frank's algorithm (in $O(m)$). In such case, filtering is only partial. Finally, based on Theorem 8, arc-consistency is obtained using $|Q|$ call to Frank's algorithm. Where $|Q|$ is the number of maximal cliques of $G$ (see Section 2.2).

<table><caption>Table 9.1: Filtering of MWIS on Chordal instances of size $n = 500$ from [37]</caption><thead><tr><th colspan="3">Instance</th><th colspan="2">Naive in O(mn)</th><th colspan="2">One PEO O(m)</th><th colspan="3">|Q|-PEO O(|Q|n)</th></tr><tr><th>name</th><th>m</th><th>d<sub>G</sub></th><th>%<sub>filt</sub></th><th>CPU</th><th>%<sub>filt</sub></th><th>CPU</th><th>|Q|</th><th>%<sub>filt</sub></th><th>CPU</th></tr></thead><tbody><tr><td>connNodes</td><td>1277</td><td>0.005</td><td>29.4</td><td><b>0.237</b></td><td>19.8</td><td>0.0</td><td>191</td><td>29.4</td><td><b>0.09</b></td></tr><tr><td>connNodes</td><td>12882</td><td>0.052</td><td>66.0</td><td>0.068</td><td>62.0</td><td>0.0</td><td>81</td><td>66.0</td><td>0.01</td></tr><tr><td>connNodes</td><td>57287</td><td>0.229</td><td>84.2</td><td>0.061</td><td>81.4</td><td>0.0</td><td>36</td><td>84.2</td><td>0.003</td></tr><tr><td>connNodes</td><td>61874</td><td>0.247</td><td>71.2</td><td><b>1.015</b></td><td>65.0</td><td>0.001</td><td>120</td><td>71.2</td><td><b>0.202</b></td></tr><tr><td>connNodes</td><td>97585</td><td>0.39</td><td>85.4</td><td><b>0.518</b></td><td>79.4</td><td>0.001</td><td>53</td><td>85.4</td><td><b>0.029</b></td></tr><tr><td>connNodes</td><td>102064</td><td>0.408</td><td>94.0</td><td>0.065</td><td>84.2</td><td>0.0</td><td>18</td><td>94.0</td><td>0.003</td></tr><tr><td>growing</td><td>12612</td><td>0.05</td><td>62.0</td><td>0.033</td><td>53.6</td><td>0.0</td><td>51</td><td>62.0</td><td>0.004</td></tr><tr><td>growing</td><td>13369</td><td>0.053</td><td>56.4</td><td>0.034</td><td>47.6</td><td>0.001</td><td>52</td><td>56.4</td><td>0.004</td></tr><tr><td>prunedTree</td><td>59585</td><td>0.238</td><td>95.6</td><td>0.073</td><td>90.6</td><td>0.0</td><td>22</td><td>95.6</td><td>0.005</td></tr></tbody></table>

In Table 9.1, results on certain instances of Caner benchmark are reported. Only instances of size $n = 500$ are reported here in order to see differences on the CPU times. Times to compute peos is considered as pre-processing time. Firstly, we can see that when using a unique peo, arc-consistency is not reached a single time but a large part of the filtering is still performed. Secondly, results on $|Q| - PEO$ validates Theorem 8, as arc-consistency is reached for every graphs. In such case, CPU's time is significantly less (one order of magnitude) than the naive implementation. In bold, we show cases where the naive implementation takes more than 0.1 second.

Since the filtering algorithm is used multiple times in the Lagrangian process, efficient filtering is important. The $|Q|-PEO$ implementation reaches arc-consistency while significantly improving computation time.

**Implementation of Algorithm 1.** The Lagrangian process (LAG) based on the Lagrangian sub-problem defined in Section 2.4 have been implemented. It uses Frank's algorithm to solve maximum weighted independent set sub-problems. Both Geometric and Newton sub-gradient algorithm have been implemented. In the results below, the sub-gradient used is Geometric, it converges slower than Newton but leads to better lower bounds. Also, Algorithm 1 have been implemented using the CPLEX solver to solve ($P_{Stable}$) with the stable sets obtained from (LAG) and the lower bound $y$. A comparison of the number of instances solved and optimally solved by the model (P) using CPLEX and by Algorithm 1 has been conducted on all small instances of the benchmark.

Table 9.2 shows results on certain graphs of the k-Tree benchmarks. First, note that on such size of instances, the solver CPLEX is in much cases very efficient. However, there is certain instances (in bold) for which it reaches its limit of time. We can see here
<table><caption>Table 9.2: Detailed results for Algorithm 1 on *k*-Tree benchmarks.</caption><thead><tr><th colspan="4">Instance</th><th colspan="3">(P)</th><th colspan="3">Lag/(P<sub>Stable</sub>)</th></tr><tr><th>name</th><th>n</th><th>m</th><th>ω</th><th>CPU</th><th>y&#773;</th><th>CPU</th><th>y&#773;</th><th>y&#773;</th></tr></thead><tbody><tr><td>5-kTree-50-3-7</td><td>50</td><td>144</td><td>4</td><td>0.27</td><td>10*</td><td>0.481</td><td><b>10</b></td><td>10*</td></tr><tr><td>9-kTree-50-5-10</td><td>50</td><td>235</td><td>6</td><td>0.85</td><td>10*</td><td>0.169</td><td><b>10</b></td><td>10*</td></tr><tr><td>9-kTree-50-7-16</td><td>50</td><td>322</td><td>8</td><td>0.37</td><td>10*</td><td>0.141</td><td><b>10</b></td><td>10*</td></tr><tr><td>4-kTree-100-5-20</td><td>100</td><td>485</td><td>6</td><td><b>600.01</b></td><td><b>11</b></td><td>17.498</td><td>9</td><td><b>11</b></td></tr><tr><td>10-kTree-100-7-33</td><td>100</td><td>672</td><td>8</td><td>110.14</td><td>10*</td><td>1.685</td><td><b>10</b></td><td>11</td></tr><tr><td>1-kTree-150-3-9</td><td>150</td><td>444</td><td>10</td><td>102.03</td><td>21*</td><td>37.106</td><td>19</td><td>22</td></tr><tr><td>1-kTree-150-5-30</td><td>150</td><td>735</td><td>6</td><td><b>600.02</b></td><td>12</td><td>34.561</td><td>9</td><td>12</td></tr><tr><td>1-kTree-150-7-49</td><td>150</td><td>1022</td><td>8</td><td><b>600.02</b></td><td>11</td><td>35.497</td><td>10</td><td>12</td></tr></tbody></table>

that most of the times, we obtain a gap of 1 with the value obtained by (P). Also, the lower bound $y$ given by (LAG) is in multiple cases equals to the optimal value. It exists multiple cases where (LAG) return a set of *independent sets* where none of them contains one of the vertices of G. In fact, sometimes it is not profitable for each color to use such vertex during the *maximum weighted independent set* resolution. In such a cases, the model (P<sub>Stable</sub>) based only on the *independent sets* obtained by (LAG) is unfeasible. To avoid it, during the creation of (P<sub>Stable</sub>), a set is created for each vertex and for each color in its domain. Using those sets can lead to sub-optimal solutions as a color is used and assigned to only one vertex. The *Lagrangian* multipliers can be used to generate several complementary independent sets per color (not just one), a technique, known in column generation as Rich Column Set [10] as also been used to improve the final upper bounds.

In Table 9.3, results over the entire benchmarks are reported.

<table><caption>Table 9.3: Comparison between Algorithm 1 and model (P) on chordal instances.</caption><thead><tr><th colspan="2">Instance</th><th colspan="4">MIP Compact</th><th colspan="4">Lag+MIP<sub>Stable</sub></th></tr><tr><th>n</th><th>name</th><th colspan="2">CPU</th><th>#<sub>s</sub></th><th>#<sub>Opt</sub></th><th colspan="2">CPU</th><th>#<sub>s</sub></th><th>#<sub>Opt</sub></th><th>Gap</th></tr><tr><th></th><th></th><th>AVG</th><th>Max</th><th></th><th></th><th>AVG</th><th>Max</th><th></th><th></th><th>Lag/up</th></tr></thead><tbody><tr><td>50</td><td>connNodes</td><td>0.073</td><td>0.26</td><td>40</td><td>40</td><td>0.233</td><td>0.603</td><td>40</td><td>21</td><td>4.875</td></tr><tr><td>50</td><td>growing</td><td>0.08</td><td>0.15</td><td>40</td><td>40</td><td>0.156</td><td>0.336</td><td>40</td><td>26</td><td>1.725</td></tr><tr><td>50</td><td>prunedTree</td><td>0.083</td><td>0.19</td><td>40</td><td>40</td><td>0.136</td><td>0.269</td><td>40</td><td>34</td><td>0.475</td></tr><tr><td>100</td><td>connNodes</td><td>1.01</td><td>5.33</td><td>40</td><td>40</td><td>0.987</td><td>5.516</td><td>40</td><td>19</td><td>12.25</td></tr><tr><td>100</td><td>growing</td><td>4.037</td><td>98.32</td><td>40</td><td>40</td><td>6.821</td><td>60.628</td><td>40</td><td>23</td><td>4.8</td></tr><tr><td>100</td><td>prunedTree</td><td>3.391</td><td>38.09</td><td>40</td><td>40</td><td>8.544</td><td>61.463</td><td>40</td><td>32</td><td>1.825</td></tr><tr><td>150</td><td>connNodes</td><td>5.509</td><td>16.84</td><td>40</td><td>40</td><td>2.313</td><td>5.824</td><td>40</td><td>21</td><td>15.2</td></tr><tr><td>150</td><td>growing</td><td>21.687</td><td><b>600.01</b></td><td>40</td><td>39</td><td>8.328</td><td>63.872</td><td>40</td><td>24</td><td>9.7</td></tr><tr><td>150</td><td>prunedTree</td><td>83.239</td><td><b>600.12</b></td><td>40</td><td>35</td><td>12.985</td><td>65.354</td><td>40</td><td>29</td><td>4.6</td></tr><tr><td>50</td><td>k-tree</td><td>0.197</td><td>0.8</td><td>180</td><td>180</td><td>0.267</td><td>0.658</td><td>180</td><td>84</td><td>0.538</td></tr><tr><td>100</td><td>k-tree</td><td>197.055</td><td><b>600.06</b></td><td>180</td><td>149</td><td>9.123</td><td>31.436</td><td>180</td><td>62</td><td>1.25</td></tr><tr><td>150</td><td>k-tree</td><td>553.363</td><td><b>600.03</b></td><td>180</td><td><b>27</b></td><td>63.121</td><td>72.45</td><td>180</td><td><b>37</b></td><td>2.6</td></tr></tbody></table>

In those results, optimality of Algorithm 1 is proved (i.e considered as optimal in
table 9.3) only when $\bar{y}$ obtained by the model ($\mathbf{P}_{\text{Stable}}$) is equals to $\underline{y}$ obtained by (LAG) or when $\omega$ (the size of the maximum clique) is equals to $\bar{y}$. However, The column Gap gives the average gap between $\underline{y}$ obtained by (LAG) and $\bar{y}$ funded by ($\mathbf{P}_{\text{Stable}}$). We can that Algorithm 1 is better on the k-trees benchmark where it is harder for the model ($\mathbf{P}$). On k-trees, $\omega(G)$ is not a lower bound as efficient as in the Caner benchmark. Thus, as it can be seen in table 9.2, in this benchmark, the Lagrangian bound is more efficient. During the Lagrangian resolution process, only maximal independent sets are kept in order to minimize the number of variable of ($\mathbf{P}_{\text{Stable}}$). However, the total resolution time of (LAG) and ($\mathbf{P}_{\text{Stable}}$) never reaches more than 70 seconds where ($\mathbf{P}$) can reach 600 seconds. In such cases, rest of the time could be use to close the gap using the model (COL) as explain in Section 8.

**Large Instances.** Finally, Algorithm 1 has been tested on a set of large instances of the Caner benchmark. Each graph is of size $n = 500$ the size of the lists are of 15% of $n$ (i.e $|C_i| = 75, \forall i \in n$). On most of the instances, CPLEX reaches the memory limit with the model ($\mathbf{P}$). Results are reported in Table 9.4.

<table><caption>Table 9.4: Results of Algorithm 1 for instances with 500 vertices</caption><thead><tr><th colspan="4">Instance</th><th colspan="3">Lag</th><th colspan="2">($\mathbf{P}_{\text{Stable}}$)</th><th>Total</th></tr><tr><th>name</th><th>m</th><th>$d_G$</th><th>$\omega$</th><th>$\underline{y}$</th><th>$\mathbf{CPU}_s$</th><th>$\#_{IT}$</th><th>$\bar{y}$</th><th>$\mathbf{CPU}_s$</th><th>$\mathbf{CPU}$</th></tr></thead><tbody><tr><td>connNodes</td><td>1037</td><td>0.004</td><td>30</td><td>26</td><td>60.34</td><td>85</td><td>30</td><td>9.25</td><td>70.41</td></tr><tr><td>connNodes</td><td>12465</td><td>0.05</td><td>127</td><td>90</td><td>32.71</td><td>150</td><td>127</td><td>1.12</td><td>34.275</td></tr><tr><td>growingSubtree</td><td>1306</td><td>0.005</td><td><b>12</b></td><td>9</td><td>55.8</td><td>286</td><td><b>21</b></td><td>10.02</td><td>65.94</td></tr><tr><td>growingSubtree</td><td>9037</td><td>0.004</td><td>68</td><td>41</td><td>21.22</td><td>170</td><td>68</td><td>11.78</td><td>34.18</td></tr><tr><td>growingSubtree</td><td>14088</td><td>0.056</td><td>172</td><td>146</td><td>14.97</td><td>191</td><td>172</td><td>3.24</td><td>19.267</td></tr><tr><td>prunedTree</td><td>12884</td><td>0.052</td><td><b>68</b></td><td>35</td><td>38.65</td><td>160</td><td><b>69</b></td><td>13.77</td><td>53.742</td></tr><tr><td>prunedTree</td><td>11565</td><td>0.046</td><td>68</td><td>38</td><td>24.46</td><td>180</td><td>68</td><td>11.86</td><td>37.286</td></tr><tr><td>prunedTree</td><td>10602</td><td>0.042</td><td>57</td><td>38</td><td>21.4</td><td>170</td><td>57</td><td>26.75</td><td>49.07</td></tr><tr><td>prunedTree</td><td>12666</td><td>0.051</td><td>162</td><td>144</td><td>14.08</td><td>210</td><td>176</td><td>2.77</td><td>17.711</td></tr><tr><td>prunedTree</td><td>12359</td><td>0.049</td><td>83</td><td>48</td><td>22.11</td><td>171</td><td>83</td><td>12.61</td><td>35.785</td></tr></tbody></table>

We can see that optimality is reached in almost all cases. However, the lower bound $\underline{y}$ given by (LAG) is rather far away from the optimal one. It is explained by either the sub-gradient algorithm converging to 0 too early or the lagrangian solver reaching its limit of time (60 seconds). However, independent sets obtained by (LAG) (and Rich Column Set) in the majority of the instances are sufficient to reach optimality using the model ($\mathbf{P}_{\text{Stable}}$). In the array, $\omega$ (the size of the maximum clique) is also reported as it guaranty optimality of the solution.

**The COLORING constraint.** A preliminary version of the constraint have been implemented on ChocoSolver. It is functional and reach arc-consistency on chordal graphs. A greedy search strategy has also been implemented to compare the CP model (COL) with the CP model (DEC) (see Section 3). As explained in Section 8, reasoning of (COL) being more efficient as (DEC), more filtering occurs and the size of the search space is
reduced. Thus, there is less nodes in the search tree. However, due to needed implementation optimizations, (COL) stays less efficient than using the model (P) on CPLEX solver. As a proof of concept, results over graphs of size n = 25 and n = 50 are given in Table 9.5. For (COL), comparison is made with the *lagrangian resolution* called only at root node and also for all node. Times and nodes are different for model (DEC) on graphs of size 50 because it was able within time to optimally solve some of them, where (COL) could not and the comparison is made only over these solved instances. The *coloring constraint* enable to cut a significant part of the search space. In the case where the *lagrangian resolution process* is called only at the root node, this gain of nodes leads to a significant gain of time. On the other hand, when the *lagrangian process* is called at all the nodes, even if the search space is even more reduced, too many time is used at each node. However, the results over the search space are encouraging.

<table><caption>Table 9.5: Comparison of the CP models with and without the *coloring constraint* for small instances where both reach an optimal solution. The same *greedy* (maximum degree over domain size first) search strategy is used to properly compare the models. The time limits was of 60 seconds.</caption><thead><tr><th rowspan="2">n</th><th rowspan="2">Lag</th><th colspan="2">(COL)</th><th colspan="2">(DEC)</th><th rowspan="2">%gain</th></tr><tr><th>CPU<sub>s</sub></th><th>#nodes</th><th>CPU<sub>s</sub></th><th>#nodes</th></tr></thead><tbody><tr><td>25</td><td>root</td><td>0,812</td><td>11597,8</td><td>1,185</td><td>20032,8</td><td>35,91</td></tr><tr><td>25</td><td>all</td><td>8,729</td><td>10500</td><td>1,185</td><td>20032,8</td><td>42,74</td></tr><tr><td>50</td><td>root</td><td>17,255</td><td>144895,7</td><td>40,898</td><td>300380,5</td><td>56,38</td></tr><tr><td>50</td><td>all</td><td>47,796</td><td>13660,3</td><td>36,754</td><td>452147,7</td><td>88,23</td></tr></tbody></table>
<figure><img src="image_20.png" /></figure>
# History of Coloring and its Industrial Uses

In 1735, the mathematician Leonhard Euler defined the first *graph theory problem*: the Königsberg bridge problem. The question asked by this problem is whether a route that traverse each of the seven bridges of the city exactly once exists. The proof that no such path exists is the first theorem in graph theory [6]. In 1852, Francis Guthrie defined the *four color conjecture*. It postulated that only four colors were sufficient to color a map such that two adjacent regions does not receive the same color. Later on, in 1879, Alfred Kempe defined the *general coloring problem* along with a proof of the *the four color conjecture*. Ten years later, this proof have been refuted by Percy John Heawood in a paper in which, based on the ideas of Kempe, he proved *the five color theorem* (every planar map can be colored with no more than five colors). In 1960, the *strong perfect graph conjecture* is formulated by Claude Berge. Respectively in 1972 and 1976, the *chromatic number problem* (i.e *k-coloring*) is proved *NP-Hard* by Richard Karp and a computer-assisted proof for the *four colors problem* on planar graphs is published by Appel and Haken. Finally, the *list-coloring* problem is defined as a generalisation of the *k-coloring* problem in 1979 [36].

In practice, the *coloring problem* finds industrial applications in scheduling and allocation problem [13, 19]. A first mention of its usage for timetabling is made in 1967 [39] and it is then used for *large scheduling problems* in 1979 [30]. The grows of the industrial usage of *coloring for schedulings* problem can be seen within the reports of the conferences *Practice and Theory of Automated Timetabling (PATAT)* [11]. A first algorithm based on *coloring* is proposed during the 2^nd^ edition in 1997. Since this edition, the *timetabling* category (notably *high school timetabling*) of each PATAT conference contains at least one algorithm based on *coloring*. Other practical usage can be noted such that *frequency allocation* [33] or *air-traffic control* [4]. A main application of *coloring* in practice is for *timetabling scheduling* problem.

The origin of *timetabling* analysis is directly connected to the usage of operations research in a military context. The first usage of *automated timetabling* dates from the *second world war* in the *british and united states* army [38]. Later on, due to a mass-production of industrial systems, *automated timetabling* has found multiple industrial usages [35].
<figure><img src="image_21.png" /></figure>
— 11 —

Exercises for the ORCO Program

Based on the results obtained during this internship, an exercise for the Master Operations Research and Combinatorial Optimizations (ORCO) has been developed. The objective of this exercise is to mobilize notions from *Graphs and Discrete Structures*, *Constraint Programming* and *Methods for Operational Research* classes.

The plan of this exercises sheet is defined as follow: at first, there is a theoretical approach of the *Maximum Weighted Independent Set* problem with modeling and complexity questions. Next, the student has to prove that *MWIS* can be polynomially solved on chordal graphs by answering a guided set of questions about the execution of Frank's algorithm. The notion of *duality* is also mobilized in the proof of this algorithm. A third exercise explores the principle of *marginal cost* and how they can be calculated using both Frank's algorithm and the *clique-tree* decomposition. A fourth exercise focus on the *constraint programming* usage of these *marginal cost*.

The first exercise is a modeling exercise that imply basic knowledge about graphs, *duality* and a reduction (or generalisation) is expected to prove the complexity of the MWIS problem. It use the notions seen in *Methods for Operational Research*. On the other hand, the second exercise is more algorithmic and based on the execution of the Frank's algorithm. It is expected of the student to understand the algorithm, to execute it and to reason on why this algorithm is optimal. It also illustrates how certain characteristics of graphs enable to polynomially solve some problems. The third exercise is the main one. It use notions and results of the first two in order for the student to investigate the principle of *reduced costs* and *marginal costs*. With the second filtering method (see Appendix A.1) the notions of *tree-decomposition* and *clique-tree* from the *Graphs and Discrete Structures* class are used along with the notion of *dynamic programming*. The last one leads the student to build a resolution based on a directed-graph modeling. This exercise allows to show how the different approaches of the classes can be melt to obtain efficient results. The last exercise shows an application of these results and it is expected from the student an understanding of the notions of *filtering and reasoning* and *arc-consistency closure*.

A context for these exercises is given with a practical example in biology in order to link this exercise to a concrete context. A complete correction has also been developed. This sheet can be found in appendix B.
<figure><img src="image_22.png" /></figure>
Conclusion

In this internship, we have presented how *arc-consistency* for the *maximum weighted independent set* on chordal graphs can be achieved in $O(|Q|m)$. Using those results, a filtering algorithm for a *COLORING* constraint based on the resolution of multiple *MWIS* sub-problems have been depicted.

We have also proposed an algorithm solving an exponential formulation of the *list-coloring* problem based on the *independent sets* obtained by *Lagrangian relaxation*. Despite the fact that the *Integer Programming* classic formulation of *list-coloring* is efficient on small instances, a preliminary set of results on large instances shows that our algorithm can give feasible solution where the *MIP* solver would reach memory limits.

Finally, a historical study of the *list-coloring* problem has been made along with its industrial applications. The last contribution of this internship is a multi-disciplinary exercises build for the next year ORCO program.

Acknowledgements

We would like to thank Oylum Seker, Pinar Heggernes, Tínaz Ekim, and Z. Caner Taskin for sending us their sets of chordal graphs. I also would like to thank my supervisor for its supervision as well as its his assistance in drafting this report.
<figure><img src="image_23.png" /></figure>
Bibliography

[1] FRANK A. Some polynomial algorithms for certain graphs and hypergraphs. *BR. COMB. CONF. 5. PROC.*, pages 211–226, 1976.

[2] Zykov A. On some properties of linear complexes. *Mat. Sb. (N.S.)*, pages 163–188, 1949.

[3] Arie M.C.A. Koster Andreas Eisenblätter, Martin Grötschel. Frequency planning and ramifications of coloring. *Discussiones Mathematicae Graph Theory*, 22(1):51–88, 2002.

[4] Nicolas Barnier and Pascal Brisset. Graph coloring for Air Traffic Flow Management. In *CP-AI-OR 2002, 4th Fourth International Workshop on Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimisation Problems*, volume 130, pages pp 163–178, Le Croisic, France, March 2002. Springer.

[5] Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, and Toby Walsh. Filtering algorithms for the nvalue constraint. In Roman Barták and Michela Milano, editors, *Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems*, pages 79–93, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.

[6] Norman Biggs, Lloyd, and Robin J. Wilson. *Graph theory, 1736-1936*. Clarendon Press, February 1986.

[7] M. Biró, M. Hujter, and Zs. Tuza. Precoloring extension. i. interval graphs. *Discrete Mathematics*, 100(1):267–279, 1992.

[8] Flavia Bonomo, Guillermo Durán, and Javier Marenco. Exploring the complexity boundary between coloring and list-coloring. *Electronic Notes in Discrete Mathematics*, 25:41–47, 2006. CTW2006 - Cologne-Twente Workshop on Graphs and Combinatorial Optimization.

[9] Raphaël Boudreault and Claude-Guy Quimper. Improved cp-based lagrangian relaxation approach with an application to the tsp. pages 1374–1380, 08 2021.

[10] Olivier Briant, Hadrien Cambazard, Diego Cattaruzza, Nicolas Catusse, Anne-Laure Ladier, and Maxime Ogier. An efficient and general approach for the joint order batching and picker routing problem. *Eur. J. Oper. Res.*, 285(2):497–512, 2020.
[11] Edmund K. Burke and Peter Ross, editors. *Practice and Theory of Automated Timetabling*, First International Conference, Edinburgh, UK, August 29 - September 1, 1995, *Selected Papers*, volume 1153 of *Lecture Notes in Computer Science*. Springer, 1996.

[12] Hadrien Cambazard and Jean-Guillaume Fages. New filtering for atmostnvalue and its weighted variant: A lagrangian approach. *Constraints*, 20(3):362–380, Jul 2015.

[13] G. J. Chaitin. Register allocation &amp; spilling via graph coloring. In *Proceedings of the 1982 SIGPLAN Symposium on Compiler Construction*, SIGPLAN '82, page 98–105, New York, NY, USA, 1982. Association for Computing Machinery.

[14] L.S. Chandran, L. Ibarra, F. Ruskey, and J. Sawada. Generating and characterizing the perfect elimination orderings of a chordal graph. *Theoretical Computer Science*, 307(2):303–317, 2003. Random Generation of Combinatorial Objects and Bijective Combinatorics.

[15] Guillaume Claus, Hadrien Cambazard, and Vincent Jost. Arc-consistency and linear programming duality: an analysis of reduced cost based filtering, 2022.

[16] Konrad K. Dabrowski, François Dross, Matthew Johnson, and Daniël Paulusma. Filling the complexity gaps for colouring planar and bounded degree graphs. In Zsuzsanna Lipták and William F. Smyth, editors, *Combinatorial Algorithms*, pages 100–111, Cham, 2016. Springer International Publishing.

[17] Clément Dallard, Martin Milanič, and Kenny Štorgel. Treewidth versus clique number. ii. tree-independence number, 2023.

[18] Runa Ganguli and Siddhartha Deb Roy. A study on course timetable scheduling using graph coloring approach. 2017.

[19] Runa Ganguli and Siddhartha Deb Roy. A study on course timetable scheduling using graph coloring approach. 2017.

[20] M. R. Garey and D. S. Johnson. *Computers and Intractability: A Guide to the Theory of NP-Completeness* (Series of Books in the Mathematical Sciences). W. H. Freeman, first edition edition, 1979.

[21] Sylvain Gravier, Frédéric Maffray, and Bojan Mohar. On a list-coloring problem. *Discrete Mathematics*, 268(1):303–308, 2003.

[22] M. Grötschel, L. Lovász, and A. Schrijver. Polynomial algorithms for perfect graphs. In C. Berge and V. Chvátal, editors, *Topics on Perfect Graphs*, volume 88 of *North-Holland Mathematics Studies*, pages 325–356. North-Holland, 1984.

[23] Martin Grötschel, Lovász László, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. *Combinatorica*, 1:169–197, 06 1981.

[24] W.K. Hale. Frequency assignment: Theory and applications. *Proceedings of the IEEE*, 68(12):1497–1514, 1980.
[25] Emmanuel Hebrard and George Katsirelos. Constraint and satisfiability reasoning for graph coloring. *Journal of Artificial Intelligence Research*, 69, 09 2020.

[26] M. Hujter and Zs. Tuza. Precoloring extension iii: Classes of perfect graphs. *Combinatorics, Probability and Computing*, 5(1):35–56, 1996.

[27] Tuza Zs. Hujter, M. Precoloring extension. ii. graphs classes related to bipartite graphs. *Acta Mathematica Universitatis Comenianae. New Series*, 62(1):1–11, 1993.

[28] Adalat Jabrayilov and Petra Mutzel. New integer linear programming models for the vertex coloring problem, 2017.

[29] Tommy R. Jensen and Bjarne Toft. Graph coloring problems. 1994.

[30] Frank Thomson Leighton. A graph coloring algorithm for large scheduling problems. *Journal of research of the National Bureau of Standards*, 84 6:489–506, 1979.

[31] Mauro Lucci, Graciela Nasini, and Daniel Severín. A branch and price algorithm for list coloring problem. *Electronic Notes in Theoretical Computer Science*, 346:613–624, 2019. The proceedings of Lagos 2019, the tenth Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019).

[32] Martin Milanič and Paweł Rzażewski. Tree decompositions with bounded independence number: beyond independent sets, 2022.

[33] Robert A. Murphey, Panos M. Pardalos, and Mauricio G. C. Resende. *Frequency Assignment Problems*, pages 295–377. Springer US, Boston, MA, 1999.

[34] Charles Prud'homme and Jean-Guillaume Fages. Choco-solver: A java library for constraint programming. *Journal of Open Source Software*, 7(78):4708, 2022.

[35] ROADEF. *Le Livre Blanc de la ROADEF*. 2019.

[36] AL Rubin, H Taylor, and P Erdos. Choosability in graphs. In *Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium*, volume 26, pages 125–157, 1979.

[37] Oylum Seker, Pinar Heggernes, Tínaz Ekim, and Z. Caner Taskin. Generation of random chordal graphs using subtrees of a tree. *CoRR*, abs/1810.13326, 2018.

[38] Charles Shrader. History of operations research in the united states army, volume 1: 1942-1962. page 223, 11 2006.

[39] D. J. A. Welsh and M. B. Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems. *The Computer Journal*, 10(1):85–86, 01 1967.

[40] L.A. Wolsey. *Integer Programming*. Wiley Series in Discrete Mathematics and Optimization. Wiley, 1998.
<figure><img src="image_24.png" /></figure>
## A
APPENDIX

### A.1 Filtering based on a maximal clique-tree decomposition

We introduce an alternative way to Frank's algorithm for solving the maximum weighted independent set in a chordal graph and compute the exact reduced cost of each vertex. This algorithm is based on dynamic programming, taking advantage of a clique-tree decomposition of the chordal graph. Its complexity is in $O(n\omega^2)$ which is higher than the $O(n\omega)$ of Frank. However, it provides the exact reduced costs of each vertex as a by-product (for free after solving) leading to an arc-consistency algorithm of the same complexity $O(n\omega^2)$. As a result, it is incomparable to the $O(|Q|m)$ based on reduced costs presented section 6.1. But more importantly, it potentially generalizes beyond chordal graphs.

Let's consider the graph $G = (V, E)$ of Figure A.1 as our running example. A single execution of Frank's algorithm is also shown on the figure as a remainder. A maximum weighted independent set is {$A, D, J, H$} for a cost of 21.

<figure><img src="image_25.png" /><figcaption>Figure A.1: Example of Chordal Graph (a) with a full execution of Frank's algorithm including a primal and dual solution.</figcaption></figure>

A chordal graph is defined as the intersection graph of subtrees in a tree. It has a maximal clique-tree decomposition (clique tree for short) i.e a tree decomposition where
each bag is a maximal clique of G. Such a decomposition $T = (V_T, E_T)$ for G is illustrated Figure A.2. Vertices C and E have been colored respectively in pink and blue to outline their corresponding subtree in T. Note also that T has been directed to state the algorithm later on easily.

<figure><img src="image_26.png" /><figcaption>Figure A.2: Example of Chordal Graph (example taken from a class of Michel Habib on Chordal graphs) with a clique tree decomposition. Note that for convenience, the decomposition has been directed from the leaves towards the root. Moreover, each bag $i$ is denoted $C_i$ ($i$-th clique) and the intersection of two consecutive bags $i$ and $j$ is denoted $\Delta_{ij} = C_i \cap C_j$.</figcaption></figure>

The dynamic program relies on the possible configurations that a bag $i$ can take in an optimal independent set. Since each bag is a clique, at most one vertex of a bag can belong to an independent set and only $|C_i| + 1$ configurations are feasible (selecting each vertex of $C_i$ alone or none). A state of the dynamic program is related to a clique $C_i$ and denoted $(a, U, i)$ where $a$ denotes the vertex selected in the independent set ($a = \perp$ if none is selected) and $U$ is the remaining unselected vertices so that $C_i = \{a\} \cup U$. $f(a, U, i)$ is the maximum value of a weighted independent set among the vertices of $\bigcup_{k=i}^{k=n} C_k$ using vertex $a \in C_i$ and none of the vertices of $U \subseteq C_i$. The value of $f$ can be computed from the states related to predecessors of $C_i$ in T. This set is denoted $\Psi^{-}(a, U, i)$ and defined as:

$$ \Psi^{-}(a, U, i) = \{(a', U', j) | C_j C_i \in E_T, a \in \Delta_{ij} \Rightarrow a' = a, U \cap \Delta_{ij} \subseteq U', C_j = U' \cup \{a'\}, a' \notin U'\} $$

Typically, $(a', U', j)$ is a predecessor of $(a, U, i)$ if (1) $C_j$ is a predecessor of $C_i$ in T (condition $C_j C_i \in E_T$), (2) the selected vertex $a$ must remain the same ($a' = a$) if it belongs to both bags $C_i$ and $C_j$ ($a \in \Delta_{ij}$), (3) unselected vertices at the intersection of both bags must remain unselected ($U \cap \Delta_{ij} \subseteq U'$) and finally (4), the definition of the state must be consistent with the bag ($C_j = U' \cup \{a'\}, a' \notin U'$).

$$ f(a, U, i) = \sum_{C_j | C_j C_i \in E_T} \max_{(a', U', j) \in \Psi^{-}(a, U, i)} (f(a', U', j) + \mathbb{1}_{a \neq \perp \cap a \neq a' w_{a'}}) $$

The underlying graph for our example is presented Figure A.3. A solution (an independent set) is an arborescence in this graph and the weight of this arborescence is the weight of the independent set. The dashed arcs show the optimal solution of weight 21 selecting the vertices A,D,H,J.
<figure><img src="image_27.png" /><figcaption>Figure A.3: Layered directed graph underlying the dynamic program based on the *clique tree decomposition* of Figure A.2. The optimal arborescence representing the optimal solution A,D,H,J of weight 21 is shown with dashed arcs. The sub-arborescence corresponding to vertex E is shown in blue matching the visual in blue of Figure A.2b.</figcaption></figure>

**Complexity.** The complexity of this dynamic programming is given by the number of arcs of the underlying dynamic programming graph. Let's denote $n$, the number of vertices of $G$ ($|V| = n$) and $\omega$ the cardinality of a maximum clique in $G$. Firstly, each $C_i$ of $T$ leads to a linear $O(\omega)$ number of states. Secondly, a key observation is that the number of maximal cliques in $G$ is at most $|V|$ (since $G$ is chordal) so $|V_T| \le |V|$ and since $T$ is a tree, $|E_T| \le |V|$ so that $E_T \in O(n)$. For each edge of the tree decomposition, the dynamic program has $O(w^2)$ arcs connected the two corresponding layers. Overall the dynamic program runs in $O(n\omega^2)$.

**Filtering.** Exact reduced cost can be computed after solving the dynamic program backward and forward. If we consider that computing $f(a, U, i)$ as defined previously is the backward step $f(a, U, i) = f^{-}(a, U, i)$. The forward step consists in computing $f^{+}(a, U, i)$ by reversing the direction of the arcs of the underlying dynamic programming graph. $f^{+}(a, U, i)$ is the maximum value of a weighted independent set among the vertices of $\bigcup_{k=1}^{k=i} C_k$ (as opposed to $\bigcup_{k=i}^{k=n} C_k$ for $f^{-}(a, U, i)$). The reduced cost of a vertex is then known by considering the sub-arborescence of a vertex and summing the missing parts using $f^{-}$ and $f^{+}$. The sub-arborescence of vertex $E$ is depicted Figure A.3. We have $f^{+}(E, \{B, C\}, 2) = 10 + 6 = 16$, $f^{-}(E, \{B, D, G\}, 3) = 1$ and $f^{-}(E, \{C, H\}, 4) = 2$. A maximum weighted independent set including $E$ costs $16 + 1 + 2 = 19$ and the exact reduced cost of $E$, $\overline{rc}(E) = 27 - 19 = 8$. The time complexity remains in $O(n\omega^2)$ since the dynamic program is applied twice in both directions.
**Generalization.** Suppose that in each bag we only need to examine a polynomial number states typically $O(n^k)$ with $k$ constant. This would be the case if we can manage to build a tree-decomposition where the number of independent sets in each bag is bounded. For instance, suppose that the graph is not chordal anymore but each bag can be covered with at most 2 cliques instead of 1, then the overall scheme applies with $O(\omega^2)$ states for each layer instead of $O(\omega)$. This approach was suggested by Maria Chudnovsky. The independence number [17, 32] of a graph G, denoted by $\alpha(G)$, is the maximum size of an independent set in G. The independence number of a tree decomposition of a graph G is the maximum, over all bags of the decomposition, of the independence number of the subgraph of G induced by the bag. The tree-independence number of G, denoted $\text{tree} - \alpha(G)$ is the minimum independence number over all tree decompositions. This parameter is bounded for a number of graphs beyond chordal graphs and the exact same algorithm presented above can be applied for solving and filtering. This suggests that the present approach could be eventually used for filtering in more general context than chordal graphs.

## A.2 Frank's Algorithms

<caption>**Algorithm 2** Maximum Weighted independent set on Chordal Graphs (Frank)</caption>

**Require:** $G = (V, E)$ a chordal graph, $W(V)$ a mapping of weights for each vertex and the PEO $\nu$ of $G$

**Ensure:** a Maximum Weighted independent set of $G$
$R \leftarrow \{\}$

for all $i = 1, \dots, |V|$ do
    $v \leftarrow \nu[i]$
    if $W(v) > 0$ then
        $R \leftarrow L \cup \{v\}$
        for all $j \in i, \dots, |V|$ do
            $u \leftarrow \nu[j]$
            if $uv \in E$ then
                $W(u) \leftarrow W(u) - W(v)$
            end if
        end for
    end if
end for
$B \leftarrow \{\}$
for all $i = |R|, \dots, 1$ do
    $v \leftarrow R[i]$
    if $u \notin R, \forall u \in N(v)$ then
        $B \leftarrow B \cup \{v\}$
    end if
end for
return $B$
## A.3 Example of Honours and Subjects Instance

This example has been taken from [18]. The objective is to find the minimum number of time slots needed to schedule a list of courses. In this example, can take one subject as Honours and two subjects as General. Let Figure A.4 represent an instance of Honours and Subjects with four Honours subjects (physics, chemistry, mathematics and economics) with their compatible general subjects.

<table><caption>Figure A.4: Example of Honours and Subjects Instance</caption><thead><tr><th>List of Honours Subjects</th><th>General Subject Combination</th></tr></thead><tbody><tr><td><i>Physics</i></td><td>Mathematicsional +<br>Computer Science/Chemistry/Electronics</td></tr><tr><td><i>Chemistry</i></td><td>Mathematicsional +<br>Physics/Computer Science</td></tr><tr><td><i>Mathematics</i></td><td>Physicsional +<br>Chemistry/Computer Science/Statistics</td></tr><tr><td><i>Economics</i></td><td>Mathematicsional +<br>Statistics/Computer Science</td></tr></tbody></table>

A valid schedule must respect the following constraints: Courses having common student cannot be allotted at the same time slot on the same day. Also, Honours and General courses need to be scheduled in non-overlapping time slots.

The problem can be transformed into a conflict graph $G$ with the following characteristics. For each course $i$, $v_i \in V$ is the vertex representing it. For each pair of courses $(i, j)$ having students and/or teachers in common, $ij \in E$ represents the no overlapping condition. Also, an edge is added between honours and general courses. Then, $\chi(G)$ correspond to the minimum of time slots needed to schedule all the lessons. Consider in Figure A.5, the conflict graph for example A.4. $\chi(G) = 4$, then the solution for the Honours and General Subject instance will be 4.
<figure><img src="image_28.png" /><figcaption>Figure A.5: Colored Conflict Graph of example A.4</figcaption></figure>
— B —

ORCO Exercise
# Marginal Costs of the Maximum Weighted Independent Set Problem in Chordal Graphs

In biology, multiple combinatorial problems can be found underneath practical ones. In this context, resolution of problems as the *maximum weighted independent set problem* can be important in disciplines such as bioinformatics or molecular biology [7]. For example, to measure the structural similarity between two molecules, the molecules are first represented as labeled graphs where the vertices and the edges correspond to the atoms of the molecule and its chemical bonds, respectively. To find the largest substructure (subgraph) that appears in both molecular graphs, it suffices to find the maximum weighted independent set of a third graph, known as conflict graph. The vertices and the edges of the conflict graph represent possible mappings and conflicts between two molecules, respectively [1].

If a particular structure is needed, certain vertices could be enforced into the solution. This operation could lead to a diminution of the optimal value of the problem. In this context, it could be useful to compute the cost of enforcing a given vertex to appear in the solution. This cost is called the *marginal cost* and we will see how it can be computed for a given vertex or for all vertices of the graph.

## Exercise 1 :

### Theoretical Questions.

A graph $G = (V, E)$ is defined over a set $V$ of vertices and a set $E$ of edges. Given a vertex $v \in V$, $N(v) \subseteq V$ is its neighborhood (i.e the set of adjacent vertices in $G$). Let $U \subseteq V$ be a subset of vertices of $G$. $U$ is a *Clique* if and only if $\forall u, v \in U, uv \in E$. Conversely, $U$ is an *independent set* (or *stable set*) iff $\forall u, v \in U, uv \notin E$. $V(U)$ is defined as the vertices of the *independent set* $U$.

The *Maximum Weighted Independent Set* problem can be defined as follow [5]:

**Weighted Independent Set**

**Instance.** A graph $G = (V, E)$, a weight $w(v) \in \mathbb{R}_+$, $\forall v \in V$, a positive real $r$.

**Question.** Does $G$ contain an *independent set* $S$ such that $\sum_{v \in S} (w(v)) \geq r$.

* Define the *MIP* formulation (**P**) of the *MWIS* problem with a constraint for each edge of $G$.

**Solution:**

$$ 
\begin{array}{lll}
\max_{x} & z = \sum_{i \in V} w_i x_i & \\
(\mathbf{P}) & \text{s.t} & x_i + x_j \leq 1, \quad \forall i,j \in E \\
& & x_i \in \{0,1\}, \quad \forall i \in V
\end{array}
\qquad (1) $$

* Define the *MIP* formulation (**P**₂) with the same variables with a constraint for each *clique* of $G$.
**Solution:**

$$ \begin{array}{ll} \max_{x} & z = \sum_{i \in V} w_i x_i \\ \textbf{(P}_2) \quad \text{s.t} & \sum_{i \in V(q)} x_i \geq 1, \quad \forall q \in \mathcal{Q} \\ & x_i \in \{0,1\}, \quad \forall i \in V \end{array} \qquad (2) $$

* Define the dual formulation (D₂) of the formulation (P₂).

**Solution:**

$$ \begin{array}{ll} \min_{y_q} & w = \sum_{q \in \mathcal{Q}} y_q \\ \textbf{(D}_2) \quad \text{s.t} & \sum_{q \in \mathcal{Q} \mid i \in V(q)} y_q \geq w_i, \quad \forall i \in V \\ & y_q \geq 0, \quad \forall q \in \mathcal{Q} \end{array} \qquad (3) $$

* Prove that, in the general case, the MWIS problem is NP-Hard.

**Solution:** The *Maximum Weighted Independent Set* problem can be seen as a generalization of the *Maximum Independent Set* problem. In fact, if $w_i = 1$ for each vertex $i$ of $G$, solving the *MWIS* problem is equivalent to solve the *maximum independent set* problem. As *maximum independent set* is *NP-Hard* in general, the *MWIS* problem is also *NP-Hard*.

## Exercice 2 : Chordal Case.

Consider the graph $G_1 = (V_1, E_1)$ in appendix. Let $O_1 = \{C, E, H, D, A, L, B, N, O, M, K, J, F, I, G\}$ be an ordering of the its vertices.

* Recall the definition of a *chordal graph*. (Give at least two characterisations)

**Solution:** Multiple definitions for chordals graphs can be given:

- A *chordal* graph contains no induced cycles of size four or more without a chord (similarly, all induced cycle are of size at most three).

- $G$ is chordal iff $G$ has a *perfect elimination ordering*. A perfect elimination ordering (*peo*) is an ordering of $V$ such that for all $v$, its neighborhood that occurs after it in this order form a clique (i.e $O = \{v_1, \dots, v_n\}$ an ordering of $V$ is a *peo* of $G$ iff $\forall v_i$, the graph induced by $N(v_i) \cap \{v_i + 1, \dots, v_n\}$ is a clique).
- G is a chordal graphs iff there exists a Clique-Tree decomposition. A tree decomposition of a graph G is a collection $\mathcal{T}$ of bags (i.e subsets of V) connected into a tree T such that: each vertex of G is in a bag; for each edge of G, both endpoints are in a bag; and for each vertex v of G, the nodes of T whose bags contain v form a sub-tree. A Clique-Tree decomposition is a valid tree decomposition in which each graph induced by a bag of T is a clique in G.

**Note:** Chordal graphs are hereditary, each induced sub-graph of a chordal graph will itself be chordal.

* Based on $O_1$, verify that $G_1$ is chordal.

**Solution:** Let consider $N^+(v_i) = N(v_i) \cap \{v_i + 1, \dots, v_n\}$ for each vertex of $G_1$. In $O_1$, $N^+(C) = \{B, G\} \quad N^+(E) = \{H, A, F\} \quad N^+(H) = \{A, F\}$
$N^+(D) = \{K\} \quad N^+(A) = \{B, F\} \quad N^+(L) = \{K\}$
we have: $-N^+(B) = \{F, G\} \quad N^+(N) = \{M, J\} \quad N^+(O) = \{K\}$
$N^+(M) = \{J, I, G\} \quad N^+(K) = \{J\} \quad N^+(J) = \{I, G\}$
$N^+(F) = \{I, G\} \quad N^+(I) = \{G\} \quad N^+(G) = \emptyset$

For each resulting set, the induced sub-graph is a clique. Thus, $O_1$ is a perfect eliminating ordering of $G_1$. By definition, as it exists a peo of the vertices of $G_1$, it is chordal.

In 1976, András Frank has defined an algorithm for the Maximum Weighted Independent Set problem on chordal graphs [2]. The algorithm require a peo and is defined over two phases:

**Forward phase.** The algorithm iterates over the vertices in the order of the peo and stops at the first vertex $v_i$ with $w'_i$ strictly positive and mark $v_i$ as red. For each vertex $v_j$ such that $j > i$ and $v_iv_j \in E$ remove $w'_i$ from $w'_j$. At any time if $w'_j$ becomes negative, it can be set to 0. Let $R$ be the set of red marked vertices obtained at the end of the algorithm.

**Backward phase.** Then, go through all red marked vertices in the reverse order and mark blue each vertex that is not adjacent to an already blue marked vertex. Let $U$ be the independent set of blue marked vertices obtained after this phase.

**Note:** The complexity of finding a peo of a chordal graph is $O(m + n)$ [3].

* In figure 2, the forward phase of Frank's algorithm is executed for the four first vertices of $O_1$. Based on this example, execute entirely Frank's algorithm on $G_1$ using $O_1$.

**Solution:** Based on $O_1$, we obtain the following execution:
<figure><img src="image_29.png" /></figure>

* Deduce a feasible solution of ($\mathbf{P}_2$) (i.e a feasible solution of ($\mathbf{P}$)) and its value.

**Solution:** Let consider the set $U^* = \{I, K, N, B, E\}$ of blue-marked vertices, by creation it as an independent set (i.e a feasible solution of ($\mathbf{P}_2$) and its value is $z^* = 37$.

* From the same execution, deduce a feasible solution of ($\mathbf{D}_2$) and its value.

**Solution:** From the execution above we obtain a set of 10 cliques. Let consider for each, a weight corresponding to the value $w'_i$ of the first red marked vertex of the clique. Doing so, we obtain a set of weighted cliques such that each vertex of $G_1$ belongs a total sum greater or equals than its original weight. Then the set $\{{\{C, B, G\} \times 6}; \{E, H, A, F\} \times 12; \{D, K\} \times 3; \{L, K\} \times 2, \{B, F, G\} \times 5; \{N, M, J\} \times 1; \{O, K\} \times 1; \{M, J, I, G\} \times 3; \{K, J\} \times 4; \{I, G\} \times 2\}$ is a feasible solution of ($\mathbf{D}_2$) and its value is $w^* = 37$.

* Conclude about the solution given by Frank's algorithm.

**Solution:** $U^*$ is a feasible solution of ($\mathbf{P}_2$) with the same value as a feasible solution of the dual problem. By the *duality theorem*, $U^*$ is an optimal solution of ($\mathbf{P}_2$) (i.e of ($\mathbf{P}$)).

* Conclude about the complexity of the *MWIS* problem on chordal graphs.
**Solution:** The complexity of Frank's algorithm is in $O(m)$ and it construct an optimal solution of (P). Thus, the *Maximum Weight Independent Set* problem on a chordal graphs can be solve in $O((m+n)+m)$ (computing a *peo* and executing Frank's algorithm). Therefore, it is polynomial and its total complexity is $O(m+n)$.

Exercice 3 :

Marginal Costs.

In a maximization (*resp.* minimization) problem, the *marginal cost* of a variable $x_i$ is the difference between the optimal value $z^*$ and the optimal value $z_i^*$, one of the best solution that contains $x_i$. It can be seen as the price to enforce $x_i$ to be a part of the solution.

Using Frank's Algorithm.

Marginal Costs of a given vertex can be computed using Frank's algorithm after altering the graph. The idea is the following, for a given vertex, for each vertex adjacent to it, set its value to 0, then execute Frank's algorithm. The solution obtained will be the *maximum weighted independent set* containing the fixed vertex. (*Note*: if its weight is negative, the vertex and its value must be added manually after execution)

* Compute the complexity to obtain the marginal costs of all vertices of a graph using such algorithm.

**Solution:** Frank's algorithm is executed once for each vertex, thus, the complexity of this method is $O(n \times m)$ (at most $n^3$).

We will now see how to compute marginal costs more efficiently.

* Recompute the previous execution of Frank's algorithm without setting values to 0 when it would become negative (when a vertex is marked red, its value is still set to 0).

**Solution:** See the solution of the first execution of Frank's algorithm.

* Consider $w'_A$, the corresponding weight of vertex $A$ at the end of this execution. What can be said about this value ? What can be said about $w'_i$ for each vertex at the end of an execution of Frank's algorithm ? (*Clue*: from the *MIP* point of view)

**Solution:** The value $w'_A$ correspond to the reduce cost of $A$ in the solution of ($\mathbf{P}_2$). It correspond to $w_A - \sum_{q \in Q|A \in V(q)} y_q$ in the dual solution built by the algorithm. The value $w'_i$ correspond to the reduce cost of each vertex $i$ in the dual solution.
* For a given peo, what can be said of vertex i in the dual in the case where i is marked in red ?

**Solution:** When a vertex is marked in red, its reduce cost in the dual is 0. It means that the corresponding constraint is tight: $w_i = \sum_{q \in Q} y_q$.

* By hand, compute $z_A^*$ on $G_1$, the value of the maximum weighted independent set that contains the vertex A. Deduce the marginal cost of the vertex A.

**Solution:** As A is in the *independent set*, B, E, F and H cannot be taken. The *maximum weighted independent set* containing A is {A, C, J, D, L, O} and its value is $z_A^* = 30$. Then the marginal cost of A is $z_A^* - z^* = 30 - 37 = -7$.

* By hand, compute $z_G^*$ on $G_1$, the value of the maximum weighted independent set that contains the vertex G. Deduce the marginal cost of the vertex G.

**Solution:** As G is in the *independent set*, B, C, F, I, M and J cannot be taken. The *maximum weighted independent set* containing G is {E, G, K, N} and its value is $z_G^* = 25$. Then the marginal cost of G is $z_G^* - z^* = 25 - 37 = -12$.

* What can be observed from the values $w'_A$ and $w'_G$ at the end of this execution.

**Solution:** At the end of this execution, $w'_A = -2$ and $w'_G = -12$. It can be observed that $w'_G$, the reduce cost of vertex G, is actually exact, it is equals to its marginal cost. However, for vertex A, its reduced cost is not exact.

* Consider $O_2 = \{N, M, D, L, O, K, J, I, C, G, B, E, A, F, H\}$, a peo of $G_1$ that end with the clique $\{E, A, F, H\}$. Execute Frank's algorithm using that peo. What can be said about $w'_A$ at the end of this execution ? What can be said about $w'_F$ and $w'_H$ ?

**Solution:** Based on $O_2$, we obtain the following execution:
<figure><img src="image_30.png" /></figure>

The solution obtained is $U_2^* = \{E, B, J, O, L, D\}$ with $z^* = 37$.

At the end of this execution, $w'_A$ is its exact reduced cost (its marginal cost). The same is true for $w'_F$ and $w'_H$.

* What can be said about a vertex that is marked in blue in at least one possible execution of Frank's algorithm ?

**Solution:** As it appears in at least one optimal solution, its marginal cost will be zero.

It is known that every chordal graph which is not a clique contains at least two non-adjacent simplicial vertices [3]. A given clique can therefore always be postponed at the very end. During the process of creation of a *peo*, when a simplicial vertex must be selected, either the resulting induced graph is *q* (the fixed clique) or it exists *v* ≠ *q* which is a simplicial vertex and can be selected first.

* From the previous answers, recall all vertices of $G_1$ with known marginal costs. Compute the minimum number of *peo* needed such that all vertices with not known marginal cost appears at least once in the last clique.

**Solution:** As $B, D, E, I, J, K, L, N$ and $O$ appears in an optimal solution (i.e have been colored in blue at least once during executions), their marginal cost are 0. With the first *peo*, the marginal cost of *G* is obtained. With the second one, the marginal cost of *A*, *F* and *H* have also been obtained. Marginal costs of *C* and *M* are not known yet. As *C* and *M* does not share a clique, two *peos* are needed. Two possible *peo* are:

$$O_3 = \{D, L, O, K, E, H, A, F, N, I, M, J, B, G, C\} \text{ and}$$

$$O_4 = \{D, L, O, K, E, H, A, F, N, B, C, G, I, J, M\}.$$
* It as been proven that each reduce cost of the last clique are actually the marginal cost of those vertices. Let $\mathcal{Q}$ be the set of maximal cliques of a chordal graph. Compute the minimal complexity needed to obtain all the marginal costs based on $\mathcal{Q}$. Compare it to the complexity of the previous method.

**Solution:** By executing Frank's algorithm for each maximal clique, marginal costs would be obtained in $O(|\mathcal{Q}|m)$. All vertices must appear at least once. By taking $G_2$, a path of five vertices, it can easily be seen that this bound is tight.

In chordal graphs, $|\mathcal{Q}| \le n$. Thus, this method is more efficient than the precedent one.

## Using a Clique-Tree Decomposition.

A tree decomposition of a graph $G$ is a collection $\mathcal{T}$ of bags (i.e subsets of $V$) connected into a tree $T$ such that: each vertex of $G$ is in a bag; for each edge of $G$, both endpoints are in a bag; and for each vertex $v$ of $G$, the nodes of $T$ whose bags contain $v$ form a sub-tree. A Clique-Tree decomposition is a valid tree decomposition in which each graph induced by a bag of $T$ is a clique in $G$. Recall that $\omega$ is the size of the maximum clique of $G$.

* Consider again the perfect eliminating ordering $O_2 = \{N, M, D, L, O, K, J, I, C, G, B, E, A, F, H\}$ and the Tree Decomposition $\mathcal{T}_1$ of $G_1$ in appendix. Build $\mathcal{T}_2$ of $G_1$, a clique tree decomposition based on $\mathcal{T}_1$ and the corresponding cliques of $O_2$. Then, direct the resulting tree such that from each bag, it exist a path to the bag containing $\{M, J, I, G\}$.

**Solution:**

<figure><img src="image_31.png" /><figcaption>Clique Tree Decomposition $\mathcal{T}_2$ based on $\mathcal{T}_1$ and $O_2$.</figcaption></figure>

We will now build another algorithm to obtain the marginal costs using dynamic programming based on this clique tree decomposition. Let's denote $C_i$ the bag $i$ (i.e the $i$-th clique). The
dynamic program relies on the possible configurations that a bag $i$ can take in an optimal independent set. Since each bag is a clique, at most one vertex of a bag can belong to an independent set and only $|C_i| + 1$ configurations are feasible (selecting each vertex of $C_i$ alone or none).

* Define the states of the *dynamic program* such that it is related to a bag $i$, a given vertex and the set of not-selected vertices of this bag.

**Solution:** States are defined as $(a, U, i)$ where $a$ denotes the vertex selected in the independent set ($a = \perp$ if none is selected) and $U$ is the remaining unselected vertices so that $C_i = \{a\} \cup U$.

* At most how many states can there be in the worst case?

**Solution:** There is a state for each vertex of each bag which is at most $\omega \times |C_i|$.

* Let $s_{ia}$ be the state corresponding for the bag $C_i$ and the selected vertex $a$. We define $f(s_{ia})$, the maximum value of a weighted independent set among the vertices of $\bigcup_{k=i}^{k=n} C_k$ using vertex $a \in C_i$ and none of the vertices of $C_i \setminus \{a\}$. The value of $f$ can be computed from the states related to predecessors of $C_i$ in $\mathcal{T}_2$. Let $\Delta_{ij} = C_i \cap C_j$ be the intersection of two consecutive bags $i$ and $j$. Define the general formulation of $\Psi^-(s_{ia})$, the set of states related to predecessors of $C_i$ in $\mathcal{T}_2$.

**Solution:** Based on the state $(a, U, i)$ we have: $\Psi^-(a, U, i) = \{(a', U', j) | C_j C_i \in E_T, a \in \Delta_{ij} \Rightarrow a' = a, U \cap \Delta_{ij} \subseteq U', C_j = U' \cup \{a'\}, a' \notin U'\}$

Typically, $(a', U', j)$ is a predecessor of $(a, U, i)$ if (1) $C_j$ is a predecessor of $C_i$ in $T$ (condition $C_j C_i \in E_T$), (2) the selected vertex $a$ must remain the same ($a' = a$) if it belongs to both bags $C_i$ and $C_j$ ($a \in \Delta_{ij}$), (3) unselected vertices at the intersection of both bags must remain unselected ($U \cap \Delta_{ij} \subseteq U'$) and finally (4), the definition of the state must be consistent with the bag $(C_j = U' \cup \{a'\}, a' \notin U')$.

* Define the recursive formula of $f(s_{ia})$.

**Solution:** Based on the state $(a, U, i)$, we obtain:

$$f(a, U, i) = \sum_{C_j | C_j C_i \in E_T} \max_{(a', U', j) \in \Psi^-(a, U, i)} (f(a', U', j) + \mathbb{1}_{a \neq \perp \cap a \neq a' w_{a'}})$$

From the dynamic program depicted above, a layered directed graph can be constructed in order to compute the value of the *maximum independent set* of a graph. An example of such a graph is presented in figure 4 on a sub-graph of $G_1$.
* In the graph (C) of figure 4, write the values on the arcs in bold.

**Solution:** The first arc correspond to selecting no vertex of {$I, F, G$}, the resulting weight is 0. The second arc correspond to selecting the vertex $G$, as the vertex appears in the arriving state, the value of this arc is also 0. The last arc correspond to taking the vertex $N$, as it does not appear in the arriving state, the value of the arc is $w_N = 1$.

* From this example, construct the underlying graph for $G_1$ based on your previous *Clique-Decomposition*, with only the arcs corresponding to the *independent set* $U_2 = \{E, B, J, O, L, D\}$ (*i.e* arcs joining states compatible with $U_2$). The value of these arcs must appear.

**Solution:** We can verify that $z^*(U_2) = 8 + 11 + 12 + 2 + 1 + 3 = 37$.

<figure><img src="image_32.png" /></figure>

* On the same graph, add the arcs needed to build the arborescence such that $A$ is taken in the solution. The value of these arcs must appear.

*Clue:* To simplify, in this case, an optimal solution such that $A$ is taken containing $J$ exists. Thus, we consider that $J$ is in the solution and all arcs that leads to a solution without $J$ do not need to be added. However, if needed, arcs not linked to $A$ or $J$ can be added if it increases the solution's value.

**Solution:** As $J$ is a part of the solution, all states containing $J$ are unchanged. States with $K$ are also unchanged as they are optimal under these conditions. As $F$ is adjacent to $A$, it cannot be taken and as $I$ and $G$ are adjacent to $F$, then state {$I, F, G$} is unchanged. As $A$ is a part of the solution, $B$ also cannot be taken and thus, the state for {$B, F, G$} becomes {$0, 0, 0$}. Finally, as $B$ and $G$ cannot be taken, $C$ is added to the
solution.

<figure><img src="image_33.png" /></figure>

* Compute the value obtain for the solution containing A. Deduce the marginal cost of A from this value and compare it with the one previously found.

**Solution:** The solution is {A, C, J, D, L, O} and its value is $z = 30$. The marginal cost of A is $30 - 37 = -7$ which is the same as found with Frank's algorithm.

Using this method, the marginal cost of each vertex can be computed during the resolution of this *dynamic program*. More precisely, consider $s_i|v \in U$ a state such that vertex $v$ is taken. Let $f^+(s_i|v \in U)$ and $f^-(s_i|v \in U)$ be the maximum sum value among compatible states after and before $s_i$, receptively. We have $z_{v \in U}^* = f^+(s_i|v \in U) + f^-(s_i|v \in U)$, the optimal value of an independent set containing vertex $v$. When solving twice in both sense this dynamic program, these two values are computed for each states ($f^+$ can be computed by reversing the arcs). Thus, $z_{v \in U}^*$ is computed for all vertices in only two iterations.

* As the complexity of this *dynamic program* is equivalent to the number of edges in the underlying layered graph, compute the complexity of this process called on a chordal graph. Recall that $\omega$ is the size of the *maximum clique*.

**Solution:** Firstly, each $C_i$ of T leads to a linear $O(\omega)$ number of states. Secondly, a key observation is that the number of maximal cliques in G is at most $|V|$ (since G is chordal) so $|V_T| \le |V|$ and since T is a tree, $|E_T| \le |V|$ so that $E_T \in O(n)$. For each
edge of the tree decomposition, the dynamic program has $O(w^2)$ arcs connected the two corresponding layers. Overall the dynamic program runs in $O(n\omega^2)$.

**Extension** Unlike the method based on Frank's algorithm, this idea could be generalised to some other classes of graphs. Suppose that in each bag we only need to examine a polynomial number states typically $O(n^k)$ with $k$ constant. This would be the case if we can manage to build a tree-decomposition where the number of independent sets in each bag is bounded. For instance, suppose that the graph is not chordal anymore but each bag can be covered with at most 2 cliques instead of 1, then the overall scheme applies with $O(\omega^2)$ states for each layer instead of $O(\omega)$. This approach was suggested by Maria Chudnovsky. The independence number [4, 6] of a graph $G$, denoted by $\alpha(G)$, is the maximum size of an independent set in $G$. The independence number of a tree decomposition of a graph $G$ is the maximum, over all bags of the decomposition, of the independence number of the subgraph of $G$ induced by the bag. The tree-independence number of $G$, denoted $\text{tree} - \alpha(G)$ is the minimum independence number over all tree decompositions. This parameter is bounded for a number of graphs beyond chordal graphs and the exact same method can be applied to compute the marginal costs.

**Exercise 4 :**

**Application to Constraint Programming**

In practice, *marginal costs* can be used to reason in *constraint programming*. Suppose a constraint MWIS($\mathcal{X}$, $G$, $W$, $l$) that takes in input a set of boolean variable $\mathcal{X}$ (a variable for each vertex of $G$), a graph $G$, a mapping of weights for all vertex of $G$ and a value $l$. The goal of such a constraint would be to filter vertices (i.e to set the corresponding boolean variable to false) that won't appear in a solution of value at least $l$.

* Consider again $G_1$ and the results of the first execution of Frank's algorithm based on $O_1$. We consider that beforehand, an heuristic on the *maximum weighted independent set* of $G_1$ gave us a lower bound $z_1 = 31$ of the optimal value. Based on the reduced costs obtained with this first execution, filter all the vertices that cannot appear in a solution of value at least $z_1$.

**Solution:** At the end of this execution, we obtain $z^* = 37$ and the reduced cost of $H$, $F$ and $G$ are respectively -8, -7 and -12. Thus, all of these vertices will be part of solutions with at most a value of 29, 30 and 25 respectively. They would be filtered by the constraint.

* Consider now all the marginal costs obtained using all the needed execution of Frank's algorithm. Using the same lower bound $z_1$, achieve *arc-consistency* for the MWIS problem over the vertices of $G_1$.
**Solution:** We recall that *arc-consistency* is achieved when no incoherent values are left. Thus, using the constraint MWIS($\mathcal{X} = \{x_A, \dots, x_O\}, G_1, W_1, \underline{z_1}$) would set $x_A, x_H, x_F$ and $x_G$ to false.

As the *maximum weighted independent set* problem is *NP-Hard* in the general case, achieve *arc-consistency* of such constraint would be *NP-hard* in this context. However, in practice, the solver could run an algorithm to check if the graph is chordal and, in such case, use Frank's algorithm to reach arc-consistency with the complexity find in exercise 3.
References

[1] Gurobi Optimization: maximum weighted independent set/clique. https://gurobi-optimods.readthedocs.io/en/stable/mods/mwis.html. Accessed: 2024-07-22.

[2] FRANK A. Some polynomial algorithms for certain graphs and hypergraphs. *BR. COMB. CONF. 5. PROC.*, pages 211–226, 1976.

[3] L.S. Chandran, L. Ibarra, F. Ruskey, and J. Sawada. Generating and characterizing the perfect elimination orderings of a chordal graph. *Theoretical Computer Science*, 307(2):303–317, 2003. Random Generation of Combinatorial Objects and Bijective Combinatorics.

[4] Clément Dallard, Martin Milanič, and Kenny Štorgel. Treewidth versus clique number. ii. tree-independence number, 2023.

[5] M. R. Garey and D. S. Johnson. *Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences)*. W. H. Freeman, first edition edition, 1979.

[6] Martin Milanič and Paweł Rzążewski. Tree decompositions with bounded independence number: beyond independent sets, 2022.

[7] Pavel A. Pevzner and Sing-Hoi Sze. Combinatorial approaches to finding subtle signals in dna sequences. *Proceedings. International Conference on Intelligent Systems for Molecular Biology*, 8:269–78, 2000.
Appendix

<figure><img src="image_34.png" /><figcaption>Figure 1: Graph $G_1 = (V_1, E_1)$ and its corresponding weights.</figcaption></figure>

<table><caption>Figure 2: Example of an execution of Frank's algorithm with the *peo* $O_1$ on $G_1$. The forward phase execution is made for the vertices C, E, H and D. For each *red* vertex, its corresponding weighted *cliques* is reported.</caption><thead><tr><th>C</th><th>E</th><th>H</th><th>D</th><th>A</th><th>L</th><th>B</th><th>N</th><th>O</th><th>M</th><th>K</th><th>J</th><th>F</th><th>I</th><th>G</th></tr></thead><tbody><tr><td>6</td><td>12</td><td>4</td><td>3</td><td>10</td><td>2</td><td>11</td><td>1</td><td>1</td><td>4</td><td>10</td><td>8</td><td>10</td><td>5</td><td>4</td></tr><tr><td>0</td><td>12</td><td>4</td><td>3</td><td>10</td><td>2</td><td>5</td><td>1</td><td>1</td><td>4</td><td>10</td><td>8</td><td>10</td><td>5</td><td>-2</td></tr><tr><td>0</td><td></td><td>-8</td><td>3</td><td>-2</td><td>2</td><td>5</td><td>1</td><td>1</td><td>4</td><td>10</td><td>8</td><td>-2</td><td>5</td><td>-2</td></tr><tr><td>0</td><td></td><td></td><td>-2</td><td>2</td><td>5</td><td>1</td><td>1</td><td>1</td><td>4</td><td>7</td><td>8</td><td>-2</td><td>5</td><td>-2</td></tr></tbody><tfoot><tr><td colspan="15">{C, B, G} × 6<br>{E, H, A, F} × 12<br>{D, K} × 3</td></tr></tfoot></table>
<figure><img src="image_35.png" /><figcaption>Figure 3: *Tree Decomposition* $\mathcal{T}_1$ of $G_1$.</figcaption></figure>

<figure><img src="image_36.png" /><figcaption>Figure 4: Example of the *dynamic programming* method on the *induced sub-graph* $G_2$ = ($\{F, G, I, J, M, N\}$, $E_1$). In (B), a directed *Tree-Decomposition* of $G_2$ and in (C), the corresponding directed graph underlying the dynamic program explained in exercise 3. The value of an arc is the weight of the vertex selected in the *independent set*. Note that when a vertex appears in multiple states, its value is reported only on the arc leaving the last state that contain it. In red, the arborescence such that *J* is in the solution. In this case, either *F* or no vertex of $\{I, F, G\}$ can be taken.</figcaption></figure>