# Several Classical Graph Problems Revisited With Tokens

Christian Laforest

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

## To cite this version:

Christian Laforest. Several Classical Graph Problems Revisited With Tokens. Clermont Université. 2025. hal-05128067

HAL Id: hal-05128067

https://hal.science/hal-05128067v1

Submitted on 24 Jun 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 - NoDerivatives 4.0 International License
# Several Classical Graph Problems Revisited With Tokens

Christian Laforest*<fnref n="1" />

¹LIMOS - Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes - Campus Universitaire des Cézeaux, 1 rue de la Chebarde, TSA 60125 / CS 60026, 63178 Aubière Cedex - France Clermont-Auvergne INP ; Mines de St Etienne ; Université Clermont Auvergne ; CNRS UMR6158.

June 24, 2025

## Abstract

In graph theory, any vertex of a graph has a given set of incident edges and neighbors. All these objects (vertices and edges) are available and can be used to produce a solution to any graph problem. In this note we explore another model: a vertex only has a limited number of its incident edges or neighbors that can be used. This restricted capability is modeled by *tokens* given to each vertex that must be assigned to them.

In this note we propose the reformulation of several classical problems (vertex-cover, domination, independent domination, connectivity, distance and spanning tree) in this model; then we propose solutions to solve them or we prove hardness results.

## 1 Introduction and notations

Many problems have been studied these last decades in the field of graph theory and graph computation (see [5] for example). In most of them, an input/instance is a graph $G$ (plus other potential data) and the goal is to construct a solution based on $G$. During the constructing process to obtain this solution, all the elements of $G$ (vertices and edges) are fully available and do not change.

More recently, alternative models have emerge. We can think of dynamic graphs where the structure of $G$ changes during periods of time<fnref n="1" />. In recent papers, we investigated other models where subsets of objects (vertices or edges) must all be part of a solution (called obligations) or pairs of objects cannot together be part of a solution (called forbidden edges or vertices). We obtained (mainly) hardness results in [3, 4, 7, 8].

In this note we deal with still another type of alternative model. Here, we give to each vertex a restrictive ability to “use” its own edges or neighbors. To model this restriction, each vertex $u$ has a given number of what we call *tokens* that can be put on its edges or neighbors, depending of the problem. Let us give more technical details and definitions now.

In this note $G = (V, E)$ is any undirected graph. An *edge* between $u$ and $v$ is noted $uv$ and edge $uv$ is *incident* to vertex $u$ (and $v$). If $G$ contains an edge $uv$ then $u$ and $v$ are *neighbors*. The set of neighbors of a vertex $u$ is $N(u)$. The *degree* of a vertex $u$ is noted $deg(u)$ and is its number

<footnote>*christian.laforest@isima.fr</footnote>

<footnote n="1">¹as this note is not devoted to dynamic graphs, no specific references are given</footnote>
of neighbors: $deg(u) = |N(u)|$. A set $S \subseteq V$ of vertices is an *independent set* of $G$ if $G$ contains no edge between vertices of $S$. A set $S \subseteq V$ of vertices is a *vertex-cover* of $G$ if any edge $uv \in E$ is *covered* by $S$, i.e. $u \in S$ or $v \in S$ (or both). A set $S \subseteq V$ of vertices is a *dominating set* of $G$ if any vertex $u \in V$ is *dominated* by $S$, i.e. $u$ is a neighbor of a vertex in $S$. A set $S \subseteq V$ of vertices is an *independent dominating set* of $G$ if $S$ is a dominating set and an independent set of $G$. A set $S \subseteq V$ of vertices is an *total dominating set* of $G$ if any vertex $u \in V$ is *dominated* by $S$ (all the vertices of $G$, even the ones of $S$, must be dominated).

It is well-known that any graph $G = (V, E)$ contains at least a vertex-cover, a dominating set, an independent dominating set and a total dominating set (in this last case, it holds when each vertex has degree at least 1). The optimisation problems associated to these notions is to construct such a set (vertex cover or some kind of domination) of minimum size. However, all the associated decision problems are NP-complete (see [6]).

Such sets of vertices can serve in practical situations to put resources (device or software) on vertices/nodes of a graph/network to do control tasks on its nodes or on its links. However, in all the graph problems described above, a vertex $u$ covers all its incident edges and dominates all its neighbors (and even itself in some variants). This means that the resource installed on a vertex has potentially enough power to control all the elements (nodes or links) connected to it. But this may be not the case. Some vertices may receive a limited power of control of their elements (for capability or energy constraints). A way to address that subject is to redefine these classical problems by limiting the possibility of covering or dominating of each vertex. This is what we do here by allocating to each vertex a certain number of *tokens* that can be used to use (cover or dominate for example) its edges or neighbors.

We suppose that each vertex $u$ of $G$ has $c(u) \ge 0$ tokens. We note $C$ this *initial distribution of tokens* to the vertices; In the following sections, an *instance* of our problems will be of the form $(G, C)$. We describe in details, in each section, the specific ways to use tokens and the associated objectives.

As we will use *network flows* to solve some of our problems and as it is a very classical subject, we just give here some notations (see [1] to get a full presentation of this vast field). A *network* is a directed graph, composed of vertices and arcs. An *arc*, directed from $u$ to $v$, is noted $(u, v)$ and its *capacity* is noted $\mathcal{C}\mathcal{A}\mathcal{P}(u, v)$. This network has two particular vertices, namely a *source* and a *sink*. In our networks, the source $s$ only has outgoing arcs (of type $(s, u)$) and the sink $t$ only has incoming arcs (of type $(v, t)$). A *flow* $x$ in a network is, for each arc $(u, v)$, a *quantity* $x(u, v)$ of flow, that must verify the *capacity constraint*: For each arc $(u, v)$, $0 \le x(u, v) \le \mathcal{C}\mathcal{A}\mathcal{P}(u, v)$ and the *conservation constraint*: For each vertex $u$, $u \ne s$ and $u \ne t$, the sum of quantity of flow ingoing in $u$ is equal to the quantity of flow outgoing from $u$. The *value* $V$ of a flow $x$ is the total quantity of flow outgoing from the source $s$ or incoming into the sink $t$. As all the capacities will be integers, computing a flow of maximal value (called maximal flow) can be done with a classical polynomial complexity algorithm (see [1]). A *nul flow* is a flow $x$ with $x(u, v) = 0$ for all arc $(u, v)$; its value is 0 of course.

## 2 Covering edges with tokens (vertex-cover with tokens)

Any graph $G = (V, E)$ has at least a trivial vertex-cover $S$, namely $S = V$, covering all the edges. In the transformation with tokens, this is not always the case. A natural goal is then to maximize the number of covered edges. This is what we do here.
In this section an assignment $\mathcal{R}$ of the instance $(G = (V, E), \mathcal{C})$ is the fact, for each vertex $u$, of putting some (or all) of the $c(u)$ tokens of $u$ to distinct incident edges of $u$. Each incident edge of $u$ can receive at most one token from $u$ but an edge $uv$ may receive a token from $u$ and another from $v$. We say that an edge $uv$ is covered by $\mathcal{R}$ if it receives at least a token (from $u$, from $v$ or both).

Given an assignment $\mathcal{R}$ of instance $(G = (V, E), \mathcal{C})$, we note $COV(\mathcal{R})$ the set of edges of $G$ covered by $\mathcal{R}$. Given any instance $I = (G = (V, E), \mathcal{C})$, the goal is to construct an assignment maximizing the number of covered edges, called *optimal assignment*. This is what we do now, by using a maximal flow. We first describe the network associated to instance $I$.

Create two new vertices, a source $s$ and a sink $t$. For each vertex $u \in V$, create a new vertex, $s(u)$ and an arc $(s, s(u))$ of capacity $c(u)$. For each edge $uv \in E$, create a vertex $r(uv)$ and three arcs of capacity 1, $(s(u), r(uv))$, $(s(v), r(uv))$ and $(r(uv), t)$. This composes the network flow $Net(I)$ associated to instance $I$. An illustration is given in Figure 1. Now, construct a maximal flow $x$ of value $\mathcal{V}$ (integer) in $Net(I)$ and extract the set $S$ of all the edges $uv$ receiving a quantity of flow of 1, namely: $S = \{uv : x(r(uv), t) = 1\}$. As the capacity of the 3 arcs incident to $r(uv)$ is 1, this quantity of flow comes either from vertex $s(u)$ or from $s(v)$ (but not both). We construct the following assignment $\mathcal{R}'(x)$, associated to $x$: the (unique) token covering edge $uv$ is either one of $u$ if $x(s(u), r(uv)) = 1$ or one of $v$ if $x(s(v), r(uv)) = 1$. This assignment covers the set of $\mathcal{V}$ edges of $S$ of $G$. Note that in this construction, any vertex $u$ can put at most $c(u)$ tokens on its incident edges, due to the limited capacity of arc $(s, s(u))$. Hence $\mathcal{R}'(x)$ is a valid assignment. Let us show now that it is optimal. Suppose by contradiction that there is another assignment $\mathcal{R}'$ covering $\mathcal{V}'$ edges with $\mathcal{V}' > \mathcal{V}$. We can suppose that any edge covered by $\mathcal{R}'$ is covered by only one token (Indeed, if an edge $uv$ is covered by a token of $u$ and a token of $v$, just delete one of these two arbitrarily. The resulting assignment covers the same edges).

Now, make the following flow $x'$. Start with a nul flow and for each covered edge $uv$, by a token of $u$, add one unit of flow on each arc of the path: $(s, s(u))$, $(s(u), r(uv))$, $(r(uv), t)$. The result is a valid flow, of value $\mathcal{V}' > \mathcal{V}$; this contradicts the fact that $x$ is a maximal flow.

To finish, note that the whole process of construction is polynomial.

## 3 Dominating vertices with tokens

In this section, a token of vertex $u$ can be put on a neighbor of $u$. Moreover, if it is also allowed to put a token of a vertex $u$ on the vertex $u$ itself, we call that the *Self model*; If this is forbidden, we call that the *Srigt model*. An assignment $\mathcal{R}$ of $(G = (V, E), \mathcal{C})$ is the fact, for each vertex $u$ of putting some (or all) of the $c(u)$ tokens of $u$ on distinct neighbors of $u$ in the *Srigt model* and possibly also on $u$ itself in the *Self model*. Each neighbor of $u$ (and $u$ itself in the *Self model*) can receive at most one token from $u$ but may receive tokens from other neighbors. We say that a vertex $u$ is *dominated* by $\mathcal{R}$ if it receives at least a token.

Given any instance $I = (G = (V, E), \mathcal{C}, \text{model})$ (with $\text{model} = \text{Srigt}$ or $\text{model} = \text{Self}$), the goal is to construct an assignment maximising the number of dominated vertices, called *optimal assignment*. This is what we do now, by using a maximal flow. We first describe the network associated to instance $I$.

Create a source $s$ and a sink $t$. For each vertex $u \in V$, construct two vertices noted $s(u)$ and $r(u)$. Create an arc $(s, s(u))$ of capacity $c(u)$. In the *Self model*, also create an arc $(s(u), r(u))$ of capacity 1 (this arc is not present in the *Srigt model*). For each edge $uv$ of $G$, create two arcs
<figure><img src="image_3.png" /><figcaption>Figure 1: A graph (with number of tokens) and its associated network</figcaption></figure>

of capacity 1: $(s(u), r(v))$ and $(s(v), r(u))$. Now, for each vertex $u$ of $G$, add an arc $(r(u), t)$ of capacity 1. Hence each vertex $r(u)$ has $deg(u)$ incoming arcs in the *Srigt* model and $deg(u) + 1$ incoming arcs in the *Self* model but only one outgoing arc towards $t$. This composes the network flow *Net*($I$) associated to instance $I$. See an illustration in Figure 2.

Now, construct a maximal flow $x$ of value $V$ (integer) in *Net*($I$) and extract $S = \{u : x(r(u),t) = 1\}$. As the capacity of each incoming arc to $r(u)$ is 1, this unique quantity of flow comes from only one vertex $s(v)$. We construct the following assignment $R(x)$, associated to $x$: the (unique) token dominating vertex $u$ comes from $v$ if $x(s(v),r(u)) = 1$ (in the *Self* model, we may have $v = u$). This assignment covers the set $S$ of $V$ vertices in $G$. Note that in this construction, any vertex $u$ can put at most $c(u)$ tokens on its neighborhood (plus $u$ itself in the *Self* model), due to the limited capacity of arc $(s, s(u))$. Hence $R(x)$ is a valid assignment. Let us show now that it is optimal. Suppose by contradiction that there is another assignment $R'$ dominating $V'$ vertices with $V' > V$. We can suppose that any vertex dominated by $R'$ is dominated by only one token (Indeed, in the reverse case, just keep only one token and delete the others. The resulting assignment dominates the same vertices).

Now, make the following flow $x'$. Start with a nul flow and for each dominated vertex $u$, by a token of $v$ ($v$ may be $u$ in the *Self* model), add one unit of flow on each arc of the path: $(s, s(u)), (s(u), r(v)), (r(v), t)$. The result is a valid flow, of value $V' > V$; this contradicts the fact that $x$ is a maximal flow.

To finish, note that the whole process of construction is polynomial.

# 4 Dominating vertices with tokens and independence constraint

Let $G = (V, E)$ be any graph. For any vertex $u$, we note $N[u] = \{u\} \cup N(u)$ (vertex $u$ and all its neighbors). In this section a token of vertex $u$ can be put on a vertex of $N[u]$. An *assignment* $R$ of $(G = (V, E), C)$ is the fact, for each vertex $u$ of putting some (or all) of the $c(u)$ tokens of $u$ on
<figure><img src="image_4.png" /><figcaption>Figure 2: A graph (with number of tokens) and its associated flow network (dashed arcs are only present in the *Self* model)</figcaption></figure>

distinct vertices of $N[u]$. Each vertex of $N[u]$ can receive at most one token from $u$ but may receive tokens from other neighbors. We say that a vertex $u$ is *dominated* by $\mathcal{R}$ if it receives at least a token. In an assignment, a vertex is *active* if at least one of its $c(u)$ tokens is used (i.e. put on a vertex of $N[u]$). In this section we only consider *independent assignments* that are assignments in which the set of active vertices form an independent set of $G$ (i.e. two active vertices cannot be neighbors). The goal here is to construct an independent assignment dominating the maximum number of vertices. The associated decision problem is the following.

**Independent Assignment Problem.**

**Instance:** $(G = (V, E), \mathcal{C})$, an integer $k \ge 1$.

**Question:** Does there exist an independent assignment for $(G = (V, E), \mathcal{C})$, dominating at least $k$ vertices?

**Theorem 1** *The Independent Assignment Problem is NP-complete, even if each vertex has exactly one token.*

**Proof.** The problem is clearly in NP. We make a reduction from the NP-complete independent set problem. An instance of this problem is any graph $G = (V, E)$ and a positive integer $k$. The question is: does $G$ contain an independent set of size at least $k$? This well-known problem is NP-complete (see [6]). Let us construct an instance of our independent assignment problem. For that we keep the same graph $G$, the same integer $k$ and for each $u \in V$, let $c(u) = 1$. Suppose that the independent set problem has a solution, i.e. there exists an independent set $S$ of $G$ with $|S| \ge k$. Now, put the token of each $u \in S$ on $u$ itself. This is an independent assignment, dominating at least $k$ vertices.

Suppose now that the independent assignment dominating problem has a solution, i.e. a set $D$ of active vertices whose tokens dominate at least $k$ vertices. Set $D$ is an independent set of $G$.
Moreover, as each vertex of $D$ has only one token, $|D| \ge k$ to dominate at least $k$ vertices. Hence the independent set problem has a solution. $\square$

# 5 Connectivity, distance preserving and spanning tree with tokens

$T = (V_T, E_T)$ is a spanning tree of a graph $G = (V, E)$ if $T$ is a tree, $V_T = V$ ($T$ spans $G$) and $E_T \subseteq E$ (edges of $T$ are edges of $G$). A well-known result asserts that $G$ is connected if and only if it contains a spanning tree. If $G$ is not connected, then it is composed of vertex-disjoint connected components.

In this section, each vertex $u$ of $G = (V, E)$ has $c(u) \ge 0$ tokens that can be put/assigned on its incident edges. If $\mathcal{R}$ is such an assignment, we note $E(\mathcal{R})$ the set of edges covered by at least a token. Then, we note $G_{\mathcal{R}} = (V, E(\mathcal{R}))$ the graph induced by all the vertices of $G$ and the set $E(\mathcal{R})$ of covered edges. Given $G_{\mathcal{R}}$, we note $\mathcal{MaxComp}(\mathcal{R})$ the number of vertices of the connected component of $G_{\mathcal{R}}$ having the maximal number of vertices. Clearly $G_{\mathcal{R}}$ is connected if and only if $\mathcal{MaxComp}(\mathcal{R}) = |V|$.

We remark that if $G = (V, E)$ is connected and if for any vertex $u$, $c(u) \ge 1$, then there exists an assignment $\mathcal{R}$ such that $G_{\mathcal{R}}$ is connected. For that, just construct any spanning tree $T$ of $G$, choose any vertex $r$, and each vertex $u$ puts a token on its incident edge on the unique path of $T$ between $u$ and $r$. In this assignment $\mathcal{R}$, each edge of $T$ receives one token, hence $G_{\mathcal{R}}$ is connected. Each vertex puts one token, except $r$, thus this construction also works if $r$ has no token. However, deciding if the largest connected component has size at least $k$ is NP-complete in the general case.

## Maximal Size Connected Component Problem.

**Instance:** $(G = (V, E), \mathcal{C})$, an integer $k \ge 1$.

**Question:** Does there exist an assignment $\mathcal{R}$ for $(G = (V, E), \mathcal{C})$, such that $\mathcal{MaxComp}(\mathcal{R}) \ge k$?

**Theorem 2** The Maximal Size Connected Component Problem is NP-complete, even if the graph is bipartite.

**Proof.** The problem is clearly in NP. We make a reduction to the NP-complete RX3C problem that is the following (see [6] and p. 125 of [9]). Let $\mathcal{X}$ be a finite set of elements and a collection $\mathcal{D}$ of triplets (sets of three elements) of $\mathcal{X}$, covering $\mathcal{X}$ i.e.:

$$ \bigcup_{Y \in \mathcal{D}} Y = \mathcal{X}. $$

Moreover, each element of $\mathcal{X}$ appears in exactly three subsets of $\mathcal{D}$; thus there are $3q$ elements and $3q$ triplets. Given such an instance $(\mathcal{X}, \mathcal{D})$ it is NP-complete to decide if there is a sub-collection $\mathcal{D}' \subseteq \mathcal{D}$ such that each element of $\mathcal{X}$ occurs in exactly one triplet of $\mathcal{D}'$. Note that if it exists, such a sub-collection $\mathcal{D}'$ has exactly $q$ disjoint triplets.

From instance $(\mathcal{X}, \mathcal{D})$, let us construct an instance of our problem. For any triplet $c_i \in \mathcal{D}$, construct a vertex, also noted $c_i$. For any element $x_i \in \mathcal{X}$, construct a vertex, also noted $x_i$, connected to the three vertices/triplets that contain it. Construct a new vertex $r$, connected to the $3q$ vertices $c_i$. All these operations give a connected and bipartite graph $G = (V, E)$. Vertex $r$ has $q$ tokens, each vertex $x_i$ has one token and all the $c_i$ have no token. We fix parameter $k = 4q + 1$.
This instance can be constructed in polynomial time. As there are exactly $q + 3q = 4q$ tokens in the instance, for any assignment $\mathcal{R}$, $\text{MaxComp}(\mathcal{R}) \le k$.

Suppose that instance $(\mathcal{X}, \mathcal{D})$ has a solution $D'$. The assignment $\mathcal{R}$ is then the following: put the $q$ tokens of vertex on the edges connecting it to the $q$ vertices of $D'$ and each vertex $x_i$ puts its token on the edge connecting it to the unique vertex/triplet of $D'$ containing it. The largest connected component contains $4q + 1$ vertices and then there is a solution to our problem.

Suppose that there is an assignment $\mathcal{R}$ of the instance $(G = (V, E), \mathcal{C})$ whose largest connected component has $4q+1$ vertices. Thus this component contains $r$ and $q$ vertices that w.l.o.g. we note $c_1, \dots, c_q$. The only way to get $3q$ more vertices connected to $r$ and $c_1, \dots, c_q$ is that the unique token of each vertex $x_i$ is put on an edge $x_i c_j$ $j = 1, \dots, q$. As, by hypothesis this is possible, this means that for each element $x_i$ there is a triplet in $c_1, \dots, c_q$ that contains it, hence the triplets $c_1, \dots, c_q$ contains all the elements and each element can only be in one of the $q$ triplets. Hence the triplets $c_1, \dots, c_q$ form a solution to the RX3C problem. $\square$

Another question is related to the possibility of preserving distances in $G$. We note $d_G(u, v)$ the distance between $u$ and $v$ in $G$, that is the length of the shortest path between $u$ and $v$ in $G$. Distance is an important concept in graph theory and has practical applications. Calculating distances is an easy task and can be done by classical algorithms (see the textbook [2]). Unfortunately, the token version is hard as we will see now.

**Distance Preserving Problem.**

**Instance:** $(G = (V, E), \mathcal{C})$, $r$ a vertex of $G$ ($r \in V$), $A$ a subset of vertices ($A \subseteq V$).

**Question:** Does there exist an assignment $\mathcal{R}$ for $(G = (V, E), \mathcal{C})$, inducing the graph $G_{\mathcal{R}}$, such that for all $u \in A$, $d_{G_{\mathcal{R}}}(r, u) = d_G(r, u)$?

**Theorem 3** *The Distance Preserving Problem is NP-complete, even if the graph is bipartite.*

**Proof.** The proof is very similar to the one of Theorem 2. We make the same (polynomial) transformation from a RX3C instance. Vertex $r$ in our problem is vertex $r$ in the construction. Vertex set $A$ of the instance is all the $3q$ vertices corresponding to $\mathcal{X}$. Note that the distances between $r$ and vertices of $A$ is 2 in the constructed graph.

As in the proof of Theorem 2, suppose that instance $(\mathcal{X}, \mathcal{D})$ has a solution $D'$. The assignment $\mathcal{R}$ is then the following: the $q$ tokens of vertex $r$ are put on the edges connecting it to the $q$ vertices of $D'$ and the unique token of each vertex $x_i$ is put on the edge connecting it to the unique vertex/triplet of $D'$ containing it. In this case, the distances between $r$ and all the vertices of $A = \mathcal{X}$ are preserved.

Suppose now that there is an assignment $\mathcal{R}$ of the instance $(G = (V, E), \mathcal{C})$ preserving the distances between $r$ and $A$. In this case, all the $q$ tokens of $r$ must have been assigned to incident edges of $r$ (otherwise some vertices of $A = \mathcal{X}$ would not be reachable). W.l.o.g. we note them $c_1, \dots, c_q$. Now, as the distances are preserved, the (unique) token of each $x_i \in \mathcal{X}$ must be put on an edge linking one of these $c_1, \dots, c_q$. This means that the $q$ sets $c_1, \dots, c_q$ cover the set $\mathcal{X}$ (each element of $\mathcal{X}$ is in at least one of these $q$ subsets).
Moreover, no $x_i$ can be part of multiple sets. Suppose that it is not the case. Then, as each set $c_i$ contains only 3 vertices, and $|\mathcal{X}| = 3q$, at least a vertex $x_i$ of $\mathcal{X}$ would not be in any $c_1, \dots, c_q$ and then the distance between $r$ and $x_i$ could not be preserved.

Conclusion: $c_1, \dots, c_q$ is an exact cover of the initial RX3C instance $(\mathcal{X}, \mathcal{D})$. □

# 6 Conclusion and Perspectives

We proposed a new model to deal with graphs, namely graphs with limited capacities of using its objects (vertices or edges). This may be useful in practical situations where resources are limited. We explored variants of classical problems and for all of them we proposed either polynomial time algorithms or hardness results.

Our tokens model may be adapted to other graph problems. Variants with particular (regular/uniform for example) initial distribution $C$ of tokens may also be taken into account.

# References

[1] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. *Network flows - theory, algorithms and applications*. Prentice Hall, 1993.

[2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. *Introduction to Algorithms, 3rd Edition*. MIT Press, 2009.

[3] Alexis Cornet and Christian Laforest. Total domination, connected vertex cover and steiner tree with conflicts. *Discret. Math. Theor. Comput. Sci.*, 19(3), 2017.

[4] Alexis Cornet and Christian Laforest. Domination problems with no conflicts. *Discret. Appl. Math.*, 244:78-88, 2018.

[5] Reinhard Diestel. *Graph Theory, 4th Edition*, volume 173 of *Graduate texts in mathematics*. Springer, 2012.

[6] Michael R. Garey and David S. Johnson. *Computers and Intractability: A Guide to the Theory of NP-Completeness*. W. H. Freeman & Co., New York, NY, USA, 1979.

[7] Christian Laforest and Timothée Martinod. On the complexity of independent dominating set with obligations in graphs. *Theor. Comput. Sci.*, 904:1-14, 2022.

[8] Christian Laforest and Timothée Martinod. Introduction to routing problems with mandatory transitions. In Leszek Gasieniec, editor, *SOFSEM 2023: Theory and Practice of Computer Science - 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023, Nový Smokovec, Slovakia, January 15-18, 2023, Proceedings*, volume 13878 of *Lecture Notes in Computer Science*, pages 254-266. Springer, 2023.

[9] C. McDiarmid. Patern minimisation in cutting stock problems. *Discrete applied mathematics*, 98:121-130, 1999.