Open problems related to integral multiow and multicut problems Appendix B: List of supervised students

Long before mobile computing changed our daily lives drastically, the development of computers, which began in the middle of the 20th century, already led scientists to study how to make use of them as eciently as possible. In particular, it led them to ask new questions such as: what can be computed by a computer? And how fast can it be computed?

Computer scientists studied such questions with the help of formal models (on which standard computers, even the most recent ones, are based), namely Turing machines. In particular, it enabled theorists to dene complexity classes for combinatorial problems, such as P and NP (both contain only decision problems) [START_REF] Garey | Computers and Intractability: a Guide to the Theory of NP-completeness[END_REF]. The complexity class a given problem belongs to then reects the kind of algorithms (in terms of running time or of required space) it can be solved with. Problems in NP can be solved in time polynomial in the size of the input by a non deterministic Turing machine, and problems in P can be solved in time polynomial in the size of the input by a deterministic Turing machine. Lots of practical combinatorial problems can be shown to be in NP, but few of them are likely to belong to P.

The work of S. Cook and R. Karp showed the existence of hard problems for NP, i.e., problems harder than any other problem in NP, as well as relations between problems in NP. Such relations are obtained via the notion of reductions, which can also be seen as transformations. If any instance of a given problem Π 1 can be transformed in polynomial time into an instance of a given problem Π 2 , then Π 1 can be polynomially reduced to Π 2 , and hence Π 2 is more general, or harder, than Π 1 . The hardest problems in NP, also called NP-complete problems, are then the ones to which any problem in NP can be polynomially reduced. Given an optimization problem, one can always dene an associated decision problem (called its decision version ), and a problem that is not in NP (as, for instance, it is not a decision problem), but is nevertheless more general than any problem in NP, is called NP-hard.

One of the main conjectures in theoretical computer science is that P is not equal to NP, i.e., that there exist problems in NP (in particular, all the NP-complete problems) that cannot be solved in polynomial time (i.e., in time polynomial in the size of the input by a deterministic Turing machine). When studying a practical problem (or its decision version), the rst question to be answered is whether this given problem is NP-complete (and hence, from this conjecture, unlikely to be in P) or not, and, if the answer is yes, then we can try to solve it practically in several ways. First, if the problem at hand is an optimization problem, then we can try to compute in polynomial time a good, but not necessarily optimal, solution. An algorithm that computes such a solution is generally called an approximation algorithm if the quality of the computed solution is guaranteed a priori (before actually running the algorithm), and a heuristic otherwise.

When considering algorithms for maximization problems, the approximation ratio of such algorithms is dened as the ratio between the optimal value and the value of the returned solution [START_REF] Vazirani | Approximation algorithms[END_REF]. (For minimization problems, just use the inverse ratio.) If this ratio is equal to 1, then the algorithm computes an optimal solution. Otherwise, the closer to 1, the better. In order to use these concepts to classify optimization problems, theoretical computer scientists have dened approximation classes for optimization problems, which are similar to complexity classes for decision problems. For instance, the class of problems that admit approximation algorithms having a ratio as close to 1 as wanted (possibly without reaching 1) is called PTAS (for Polynomial-Time Approximation Schemes ). Another example is the class of problems that admit approximation algorithms having a constant ratio, which is called APX. The hardest problems for APX, which are not in PTAS (unless P equals NP), are called APX-hard (or APX-complete if they are in APX).

Second, we can express the problem that must be solved with the help of some classical model in mathematical programming, such as linear programming with integral variables (also called integer linear programming), and then solve the problem using suitable algorithms (such as Branch & Bound ). Obviously, the running time of such algorithms is not guaranteed to be polynomial, but in practice one can hope they run faster than a basic exhaustive search, in particular when implemented in a commercial solver.

Third, one can solve a more restricted problem, by considering real-life additional constraints or imposing a special (but relevant) structure on the instances to be solved, in the hope that this may yield an easier problem (e.g., one that belongs to P). Another way of restricting the problem is to assume that, in practice, some part of the input (called a parameter ) is small. This is the basic idea in the eld of parameterized complexity, which extends classical computational complexity [START_REF] Downey | Parameterized Complexity[END_REF]. Given a parameter k for a problem Π, an algorithm solving Π is FPT (or Fixed-Parameter Tractable ) with respect to k if it runs in time O(f (k)n c ), where f (•) is any computable function, n is the size of the input, and c is a constant. In other words, the non-polynomial part in the running time only depends on k. The class FPT is then the one of parameterized problems admitting FPT algorithms. Other parameterized classes named W [START_REF] Adamy | Call Control in Rings[END_REF], W [START_REF] Arkin | The (K, k)-Capacitated Spanning Tree Problem[END_REF], etc., have been dened, and contain problems harder than the ones in FPT. Actually, the relationship between FPT and W [START_REF] Adamy | Call Control in Rings[END_REF]/W [START_REF] Arkin | The (K, k)-Capacitated Spanning Tree Problem[END_REF]/etc. is similar to the one between P and NP: a parameterized problem that is W [START_REF] Adamy | Call Control in Rings[END_REF]-hard/W [START_REF] Arkin | The (K, k)-Capacitated Spanning Tree Problem[END_REF]-hard/etc. is unlikely to be FPT, unless some very likely conjecture in parameterized complexity collapses.

We shall present in Section 1.2 the class of combinatorial problems that we will be interested into throughout this report, as well as its general structure, and then provide in Section 1.3 some basic NP-complete problems, as well as some notions from graph theory that will be useful.

General presentation of the report

In this report, I shall review all the results, related to several covering and packing problems in graphs, that were obtained with dierent co-authors since 2003. Assume we are given an m × n matrix A = (a ij ) and two vectors b and c of respective sizes m and n, which are such that all a ij 's, all b i 's and all c j 's are positive rational numbers. A packing problem is a problem that can be modelled as the following (integer) linear program: x j ≥ 0 (x j ∈ N) ∀j ∈ {1, . . . , n}

A covering problem is a problem that can be modelled as the following (integer) linear program:

min n j=1 c j x j s. t. n j=1 a ij x j ≥ b i ∀i ∈ {1, . . . , m} (1.2)
x j ≥ 0 (x j ∈ N) ∀j ∈ {1, . . . , n}

In both cases, the x j 's can take any positive real values, or only positive integral values, depending on the problem that is considered. When the x j 's are not required to take positive integral values, the problem can be solved in time polynomial in n and m as a linear program. Otherwise, the problem generally becomes hard. We shall give examples of such packing and covering problems in the next section of this chapter, and also throughout the report.

The rst of my articles that needs to be mentioned here is [START_REF] Bentz | Packing and covering with linear programming: A survey[END_REF]. This article deals with the issue of modeling and solving packing and covering problems in graphs using linear programming: it was written with Denis Cornaz and Bernard Ries, and greatly inspired the presentation of this report. Indeed, the general idea on which this article is based is that all kinds of packing and covering problems in graphs share, to some extent, some common principles, such as the fact that, while nding (near-)optimal solutions is often a hard task, nding provably good feasible solutions may be easy.

Any constraint having the same form as Constraints (1.1) will be called a packing constraint, and similarly any constraint having the same form as Constraints (1.2) will be called a covering constraint. In this report, we shall also consider packing problems with additional covering constraints, or covering problems with additional packing constraints. In other words, we shall consider packing problems, covering problems, as well as combinatorial problems with both packing and covering constraints.

The general structure of the present report is as follows. In the next section, we describe the basic notions and problems that will be needed to read and understand the remainder of the report. In Chapter 2, we study a pair of related packing and covering problems, which respectively generalize the maximum ow and minimum cut problems: namely, the maximum integral multiow problem and the minimum multicut problem, as well as some of their variants. In Chapter 3, we study several problems consisting of coloring the vertices of a graph, i.e., covering them by colors, under dierent types of cardinality constraints, which can naturally be seen as packing constraints.

In Chapter 4, we study d-transversal problems, i.e., problems consisting of covering a given number d of times all the optimal solutions of a given graph optimization problem. Finally, in Chapter 5, we study several variants of the Steiner tree problem, which asks to cover, by a connected subgraph (called a Steiner tree), some pre-specied vertices (called terminals) of a graph.

Basic notions and problems

We shall now review the basic notions and problems that we will need in the remainder of the report.

Cook's Theorem states that the satisability problem (called SAT), a basic problem in propositional logic, is NP-complete [START_REF] Garey | Computers and Intractability: a Guide to the Theory of NP-completeness[END_REF]. Assume we are given a set of boolean variables x 1 , x 2 , . . . (each variable x i having two associated literals, namely x i itself and its negation xi ) and a set of clauses, each one of them being a disjunction of some the literals associated with the boolean variables. Then, each clause among this set of clauses is satised, i.e., of value true, if at least one of its literals is true. The problem SAT consists in determining whether there exists a truth assignment (i.e., a way of giving a value true or false to each variable), called satisfying truth assignment, for CHAPTER 1. INTRODUCTION 7 which all clauses are satised. Variants of this problem can be obtained, in particular, by restricting the number of literals by clause and/or adding an objective function. For instance, the problem called 3SAT is the special case of SAT where each clause contains at most three literals, and the problem called Max2SAT is the variant of SAT where each clause contains at most two literals, and the problem consists in determining the maximum number of clauses that can be satised by a truth assignment. Both these variants, as well as other similar variants, remain NP-hard (NP-complete for 3SAT). This is the case, for instance, for the problem Monotone1-in-3SAT, a variant of 3SAT that will be detailed when needed.

Throughout the report, we shall also need some basic graph notions. We will describe the main ones here, but, for any other basic notion not dened here, the reader can refer to any book about graph theory, should it be needed. Given a graph G, the line graph of G is the graph where there is one vertex for each edge of G, and an edge between two of its vertices if the associated two edges in G share a vertex. A graph G is bipartite if its vertex set can be partitioned into two sets L (for Left ) and R (for Right ) such that, for any edge uv of G, we have u ∈ L and v ∈ R. A graph is complete if there is an edge between any two of its vertices, and we dene the complement of a graph G with n vertices as the graph obtained from G by taking a complete graph on the n vertices of G, and then removing from this complete graph the edges of G. A subgraph (i.e., a subset of vertices and/or edges) of a graph G is a clique if it is a complete graph in its own right.

Given a graph G, apart from cliques, we can dene other types of subgraphs: for instance, a stable set in G is the complement of a clique in G, a matching in G is a set of vertex-disjoint edges, and a vertex cover in G is a set of vertices of G that contains at least one vertex of each edge of G.

In fact, for each of these four types of subgraphs, we can dene an associated graph optimization problem, by searching, in a graph G, the maximum size (or minimum size, for a vertex cover) of such a subgraph, which will simply be called the stability number of G in the case of a stable set. All the problems obtained in this way are NP-hard in general, except nding a matching of maximum size, which can be done in polynomial time. However, they can all be solved in polynomial time in bipartite graphs: in particular, the famous König's Theorem for bipartite graphs states that, in such graphs, the maximum size of a matching equals the minimum size of a vertex cover.

A notion related to stable sets is the one of proper colorings : a proper (vertex) coloring of a graph G is an assignment of colors (for instance, numbers) on the vertices of G, such that any two adjacent vertices receive different colors. Such a coloring can also be seen as a partition of the vertices of G into stable sets (one for each color). The minimum number of colors needed for a proper coloring of a graph G is called the chromatic number of G, and is denoted by χ(G): computing χ(G) is NP-hard in general, but we have χ(G) ≤ 2 in any bipartite graph G (as L and R are two stable sets).

We end this section by describing a graph parameter that can be seen as a measurement of the tree-likeness of a graph. Indeed, not all graphs are trees, and bipartite graphs are not the only relevant generalizations of trees.

A tree decomposition of a graph G = (V, E) is a pair {X i |i ∈ I}, T where X i ⊆ V, ∀i ∈ I, are bags of vertices of G, T = (I, F ) is a tree, and:

(1)

i∈I X i = V , (2) For every edge uv ∈ E, there is an i ∈ I such that u, v ∈ X i , (3)
For all i, j, l ∈ I, if j lies on the path between i and l, then X i ∩X l ⊆ X j .

The width of a given tree decomposition of a graph G equals max i∈I |X i |-1. The tree-width of a graph G, denoted by tw(G), is the minimum width of a tree decomposition of G, taken over all tree decompositions of G. Note that trees (and hence chains and stars) have tree-width 1. Without loss of generality, we can also assume that the tree decomposition is nice [START_REF] Kloks | Computations and Approximations[END_REF], i.e.:

• T is rooted at some node r,

• T is binary and has O(|V |) nodes,

• If a node i has two children j and k then X i = X j = X k (join node)

• If a node i has one child j, then either

(a) |X i | = |X j | -1 and X i ⊂ X j (forget node) (b) |X i | = |X j | + 1 and X j ⊂ X i (introduce node)
Given two vertices i, j of T , we will use the notation j i to denote the fact that j is either i or a descendant of i with respect to r. Given a node i ∈ I, let Y i = E ∩(X i ×X i ), i.e., Y i is the subset of E induced by the vertices in X i . Moreover, let T i = j i X j and let G[T i ] be the subgraph of G induced by T i .

Chapter 2

Integral multiows & multicuts 2.1 Introduction

In this chapter, we review results about integral multiow and multicut problems, which form a pair of related packing and covering problems, respectively. I started studying such problems during my PhD thesis [START_REF] Bentz | Résolution exacte et approchée de problèmes de multiot entier et de multicoupe : algorithmes et complexité[END_REF], and I have continued to work on some related open questions after I defended it in 2006. In both problems, we are given an edge-capacitated graph G = (V, E) (directed or not) and a list of source-sink pairs (s i , s i ).

The basic versions of such problems can be modeled by two linear programs with integral variables (ILP). The rst one models the maximum integral multiow problem (MaxIMF), and is as follows:

max |P| j=1 f j (ILP-IMF ) s. t. j s. t. e∈pj f j ≤ capa(e) ∀e ∈ E (2.1) f j ∈ N ∀j ∈ {1, . . .

, |P|}

where P = i {simple paths linking s i to s i }, capa(e) is the capacity of edge e, p j is the jth path of P, and f j is the amount of ow routed on p j .

The maximum integral multiow problem hence consists in routing as much ow units (i.e., integral amounts of ow) as possible on the paths of P (i.e., linking one source s i to its corresponding sink s i ) while respecting the capacity constraints on the edges, and therefore it is a packing problem.

Note that the case where all capacities are equal to 1 is actually an important special case of MaxIMF. In this case, no path can carry more than 1 unit of ow, and at most one path from P carrying 1 unit of ow can go through each edge. This case hence consists in routing the maximum number of edge-disjoint paths from P, and is known as MaxEDP.

CHAPTER 2. INTEGRAL MULTIFLOWS & MULTICUTS

z e ∈ {0, 1} ∀e ∈ E
where z e is equal to 1 if edge e is selected, and 0 otherwise. MinMC hence consists in selecting a set of edges of minimum total capacity, such that any path in P (i.e., linking one source s i to its corresponding sink s i ) contains at least one such edge, and therefore it is a covering problem.

Actually, the continuous relaxations of these ILPs are two dual linear programs (simply associate a nonnegative dual variable z e to every constraint (2.1)). Moreover, the number of variables in (ILP-IMF ) is exponential, as is the number of constraints in (ILP-MC ). There also exist alternative ILPs for these two problems that have a polynomial number of variables and constraints (by using ow-based variables), but we will not need them. However, these other ILPs imply that the continuous relaxations of MaxIMF and MinMC can be solved in polynomial time: in the case of MaxIMF, this corresponds to the maximum multiow problem, i.e., for each pair (s i , s i ), the amount of ow routed from s i to s i on each edge can be non integral.

One of the main consequences of the duality between these formulations is that many researchers have worked on nding relevant special cases where MaxIMF and MinMC have the same optimal value (as in the continuous case, by strong duality in linear programming) or optimal values that are close to each other (if one is only interested in good solutions for both problems), as well as exhibiting sucient conditions ensuring such properties.

In the next section, we shall review some of our results related to such questions, and in the subsequent sections we shall deal with the complexity of both MaxIMF and MinMC in dierent cases. Also note that some open problems related to this chapter are given in Appendix A.

Solving MaxIMF & MinMC by using duality

The rst remark of this section is simply a direct consequence of the duality relationship between the continuous relaxations of the ILPs modeling a polynomial-time algorithm that computes such a pair of solutions with α = 2, when G is a tree [START_REF] Garg | Primal-dual approximation algorithms for integral ow and multicut in trees[END_REF]. Their algorithm is guided by the complementary slackness (or optimality) conditions in linear programming, in order to compute C from F : such algorithms are called primal-dual algorithms. Thus, when α is small enough (e.g., a constant), designing approximation algorithms in such a way implies in particular that the associated optimal values of MaxIMF and MinMC are not too far away from each other.

The case where α = 1 simply implies that the associated instances of MaxIMF and MinMC have the same optimal values: in such a case, the reasons behind this fact often lie in some properties of the underlying linear programming formulation, which we shall discuss.

When trying to solve a hard combinatorial problem in the context of a real-life application, one tends to use simple (and easy-to-implement) heuristics, with or without guaranteed quality performance. As far as MaxIMF is concerned, with applications ranging from routing through telecommunication networks to wiring in VLSI circuits, one of the best known and most used heuristics is the simple following one [START_REF] Kleinberg | Approximation algorithms for disjoint paths problems[END_REF]:

SP F

While P is not empty do:

1. Route as much ow as possible on the shortest path p in P,

2. Update the residual capacities, and delete any edge with residual capacity equal to 0, as well as any vertex that becomes isolated, 3. Remove from P the path p and any other path containing at least one deleted edge.

As indicated, we will refer to this heuristic as SP F (for Shortest Path First ).

It should be noticed that, although P may contain an exponential number of paths, SP F can be implemented to run in polynomial time, since in practice it amounts to computing a shortest path in a residual graph at most O(|E|) times, without actually deleting paths from P (the deletion of an edge usually resulting in the deletion of an exponential number of paths from P).

It is known for a long time that SP F has an approximation ratio of O( |E|) in terms of |E| [START_REF] Kleinberg | Approximation algorithms for disjoint paths problems[END_REF] To overcome this shortcoming, a heuristic that essentially routes ow iteratively along a set of spanning trees was proposed in [START_REF] Bentz | Disjoint paths in sparse graphs[END_REF], and its performance was studied theoretically under some specic conditions. Moreover, a variant of the following approximation algorithm, combining SP F with the previously mentioned heuristic, was also suggested:

AH4M AXIM F

• For λ ranging from 0 to |V | do:

1. While there remain paths in P of length at most λ, run SP F on G. Let G be the graph obtained from G at the end of this step.

2. Compute a spanning tree with maximum total capacity on each connected component of G , using essentially Kruskal's algorithm.

3. Run the approximation algorithm of Garg et al. [START_REF] Garg | Primal-dual approximation algorithms for integral ow and multicut in trees[END_REF] on each tree S obtained at Step 2, to get a feasible integral multiow F S and a feasible multicut C S on S such that val(C S ) ≤ 2•val(F S ). Update the residual capacities, and delete from G any edge with residual capacity equal to 0, as well as any vertex that becomes isolated.

4. If val(F S ) > 0 for some S, then go to Step 2.

• Output the best solution obtained, where each solution is the combination of the solution computed at Step 1 for a given λ and of the solution computed by going through Steps 2 to 4 for this same λ.

We will refer to this heuristic as AH4M AXIM F (for Another Heuristic For MAXimum Integral MultiFlow ), and to the heuristic consisting only of ning tree obtained at Step 3 is not computed as a maximum spanning tree (in which case we shall give details about how it is computed).

Note that the solution computed by AH4M AXIM F is at least as good as the one computed by SP F (thanks to the case λ = |V |) and as the one computed by M ST + GA (thanks to the case λ = 0). Moreover, apart from SP F and AH4M AXIM F , there are not many heuristics specically known for MaxIMF. However, it should be mentioned that Chekuri, Khanna and Shepherd have written an impressive series of papers where they investigated approximation algorithms for MaxIMF when the tree-width of the graph is small, or when the minimum capacity is a small integer larger than or CHAPTER 2. INTEGRAL MULTIFLOWS & MULTICUTS 13 equal to 2. Unfortunately, these algorithms are quite involved, quite hard to implement, and thus unlikely to be used in practice [START_REF] Chekuri | Edge-Disjoint Paths in Planar Graphs[END_REF][START_REF] Chekuri | Multicommodity ow, welllinked terminals, and routing problems[END_REF][START_REF] Chekuri | A Note on Multiows and Treewidth[END_REF][START_REF] Chekuri | Edge-Disjoint Paths in Planar Graphs with Constant Congestion[END_REF].

The initial intuition behind ST + GA was that, thanks to Garg et al.'s 2approximation algorithm for MaxIMF in trees [START_REF] Garg | Primal-dual approximation algorithms for integral ow and multicut in trees[END_REF], we know an ecient and easy way of routing a good integral multiow in a tree, whereas MaxIMF remains APX-hard in this case. Moreover, this algorithm uses only basic graph algorithms (essentially a breadth-rst search, and the computation of a set of least common ancestors ), so it is rather simple to implement. Therefore, using this algorithm as a subroutine inside a more general one seemed like a sound idea, provided that under relevant assumptions this would still yield good theoretical approximation ratios.

The seminal paper of Garg et al. studying MaxIMF and MinMC on trees [START_REF] Garg | Primal-dual approximation algorithms for integral ow and multicut in trees[END_REF] inspired many research papers, which generalized or improved these results in some way. For instance, one can notice that their approximation ratio of 2 is, in this case, 2(γ(G)+1), where γ(G) is the cyclomatic number of G (with γ(G) = 0 if G is a tree, by denition). Actually, the rst motivation for introducing M ST + GA was to prove the following set of results: Theorem 2.1 [START_REF] Bentz | Edge disjoint paths and max integral multiow/min multicut theorems in planar graphs[END_REF][START_REF] Bentz | Disjoint paths in sparse graphs[END_REF]). All the tractability and approximability results proved in the paper of Garg, Vazirani and Yannakakis [START_REF] Garg | Primal-dual approximation algorithms for integral ow and multicut in trees[END_REF] can be generalized to undirected graphs with bounded cyclomatic number.

In other words, the approximation results in [START_REF] Bentz | Disjoint paths in sparse graphs[END_REF] were proved by making use of M ST + GA. However, Garg et al. also proved other results, which we will not fully describe here, such as the polynomial-time solvability of MaxEDP, i.e., the special case where all capacities are 1, and so where we look for edge-disjoint paths: this theorem states that these other results hold in undirected graphs with bounded cyclomatic number as well, while this is not true for other natural generalizations. For instance, MaxEDP becomes APX-hard even in some specic families of cacti (i.e., graphs where any two cycles share no common edge). It should be noticed that a graph G with cyclomatic number γ(G) has tree-width O(γ(G)) (so having bounded cyclomatic number is a special case of having bounded tree-width), and that the complete graph K t has tree-width t -1 and cyclomatic number Θ(t 2 ). Hence, the family of graphs G with cyclomatic number γ(G) = O(1) contains graphs with (constant but) arbitrarily large tree-width: a graph G with cyclomatic number γ(G) can have tree-width Ω( γ(G)).

In contrast with Theorem 2.1, there exist cases where applying Garg et al.'s algorithm on a maximum spanning tree of the input graph does not always yield a good solution for the whole graph. This is why the variant ST + GA was also considered: the choice of the spanning tree on which Garg et al.'s algorithm will be applied must then be made according to some rules, which can depend on the structure of the underlying graph. Let us now describe an application of this idea, which also appeared in [START_REF] Bentz | Disjoint paths in sparse graphs[END_REF].

CHAPTER 2. INTEGRAL MULTIFLOWS & MULTICUTS 14

There exist several ways of expressing the fact that a graph is tree-like, and the more a graph resembles a tree, the more applying ideas that worked well for trees is likely to yield good results in such a graph as well. One such way (actually a rather classical one) is to consider graphs with bounded tree-width, and one of the most widely known classes of planar graphs with bounded tree-width is the class of k-outerplanar graphs for k = O(1).

Roughly speaking, a planar graph is a k-outerplanar graph if removing at most k times its vertices lying on the outer face (and updating the outer face accordingly after each such removal) results in a graph with no vertex. In [START_REF] Bentz | Disjoint paths in sparse graphs[END_REF], I introduced a new subclass of k-outerplanar graphs called k-edgeouterplanar graphs. The denition of such graphs is easily obtained from the previous one by replacing vertex by edge.

It is rather easy to see that any k-edge-outerplanar graph is also a kouterplanar graph, but the converse is not true in general (for instance, the complete bipartite graph K 2,t is 2-outerplanar but t 2 -edge-outerplanar).

However, it was proved in the same paper that, if the degree of any vertex is bounded inside each block of a k-outerplanar graph with k = O(1), then this graph is also k -edge-outerplanar for some k = O(1). A wheel graph, or any Halin graph (i.e., any planar graph obtained by connecting the leaves of a tree into a cycle), provides an example showing that such a condition is not necessary for a k-outerplanar graph with k = O(1) to be k -edge-outerplanar for some k = O(1). Also note that, if a graph is either a k-outerplanar graph or a k-edge-outerplanar graph, then it has tree-width O(k).

There exist simple and classical families of graphs which are k-edgeouterplanar (and hence also k-outerplanar) for some k = O(1). For instance, any rectilinear grid with Θ(k) rows and columns has tree-width Θ(k), and is both a Θ(k)-outerplanar and a Θ(k)-edge-outerplanar graph. Such graphs provide a way of showing, in particular, that the class of k-edge-outerplanar graphs with k = O(1) contains graphs with (constant but) arbitrarily large tree-width, which means that, for any constant K, there is a Θ(K)-edgeouterplanar graph whose tree-width is at least K.

Using ST + GA, where the spanning tree is computed level by level (and so is not a maximum spanning tree), as well as an additional step during which a feasible multicut for the whole graph is computed based on the one for the spanning tree, we obtain the following result:

Theorem 2.2. [START_REF] Bentz | Disjoint paths in sparse graphs[END_REF] Given any k-edge-outerplanar graph with capacities 1, a feasible integral multiow F and a feasible multicut C satisfying val(C) ≤ 4k • val(F ) can be computed in polynomial time.

An easy consequence is the following result:

Corollary 2.1. There exists a family of graphs of bounded (but arbitrarily large) tree-width, containing the rectilinear grids with at least one bounded dimension, in which the ratio between the optimal values of MinMC and MaxIMF is O(1), provided that all capacities are O(1).

CHAPTER 2. INTEGRAL MULTIFLOWS & MULTICUTS 15

To the best of our knowledge, this result provides the only known class of graphs of bounded (but arbitrarily large) tree-width in which the optimal values of MinMC and MaxIMF are close, i.e., for which the ratio between these two optimal values is O(1), and moreover for which this ratio is linearly related to tw(G), the tree-width of the input graph G, as this ratio is actually O(tw(G)). Indeed, the algorithm of Chekuri, Khanna and Shepherd in [START_REF] Chekuri | A Note on Multiows and Treewidth[END_REF] shows that, in graphs of bounded tree-width, this ratio is Later, the authors of [START_REF] Seguin-Charbonneau | Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2[END_REF] conrmed the intuition that MaxEDP is actually the hardest case by proving that, if the minimum capacity is 2, essentially excluding the case of MaxEDP, then the ratio between the optimal values of MinMC and MaxIMF is O(1) in undirected planar graphs. (Recently, a polylogarithmic ratio was proved in general undirected graphs [START_REF] Chuzhoy | A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2[END_REF].)

However, applying M ST + GA on 1-edge-outerplanar graphs, which we shall simply call edge-outerplanar graphs (or cacti), together with an additional step during which a feasible multicut for the whole graph is computed based on the one for the maximum spanning tree, yields both a feasible integral multiow F and a feasible multicut C satisfying val(C) ≤ 4 • val(F ) [START_REF] Bentz | Disjoint paths in sparse graphs[END_REF], while Erlebach obtained a 3-approximation for MaxEDP in 2edge-connected edge-outerplanar graphs (also called trees of rings ) [START_REF] Erlebach | Approximation algorithms and complexity results for path problems in trees of rings[END_REF].

We now go back to the case of rectilinear grids. A lot of decision problems related to the existence of edge-disjoint paths in such graphs and slightly more general ones have been studied before 1990 [START_REF] Frank | Disjoint paths in a rectilinear grid[END_REF][START_REF] Frank | Edge-disjoint paths in planar graphs[END_REF][START_REF] Kaufmann | Routing problems in grid graphs[END_REF]: when the sources and sinks can lie anywhere inside the grid, the problem of deciding whether edge-disjoint paths linking s i to s i for each i simultaneously exist is NP-complete, even if some parity condition on the degrees (after adding an edge between each pair (s i , s i )), called Eulerian condition, holds [START_REF] Marx | Eulerian disjoint paths problem in grid graphs is NPcomplete[END_REF].

However, the problem is easier if all sources and sinks lie on the outer face. In particular, Frank gave necessary and sucient conditions for the existence of such disjoint paths in this case [START_REF] Frank | Disjoint paths in a rectilinear grid[END_REF], and later extended this characterization to planar graphs where all sources and sinks lie on the outer face, and any vertex not on the outer face has even degree [START_REF] Frank | Edge-disjoint paths in planar graphs[END_REF].

In [START_REF] Bentz | Maximum integer multiow and minimum multicut problems in two-sided uniform grid graphs[END_REF], we studied MaxIMF and MinMC in particular rectilinear grids called two-sided, in the hope that the strong results concerning the existence of disjoint paths in grids could be used to solve related optimization problems eciently. A two-sided grid is a rectilinear grid where all sources and sinks lie on the uppermost and lowermost rows of the grid, and at most one source/sink can lie on each vertex of these two rows. Furthermore, as

Frank, we implicitly assume that, for each i, s i and s i can be linked by at most one path: therefore, in this case, solving MaxEDP is equivalent to nding the maximum number of source-sink pairs (s i , s i ) that can simultaneously be linked by edge-disjoint paths in the grid.

A well-known necessary condition for the existence of edge-disjoint paths between s i and s i for each i in a graph G = (V, E) is the cut condition : for each W ⊂ V , the number of edges of E having one endpoint in W and one endpoint in V \W must be greater than or equal to the number of pairs (s i , s i ) such that one of {s i , s i } lies in W and the other one in V \ W . Okamura and Seymour showed in particular that, in a planar graph that satises the Eulerian condition and where all sources and sinks lie on the outer face, this condition is necessary and sucient for the existence of disjoint paths [START_REF] Okamura | Multicommodity ows in planar graphs[END_REF].

Note that a two-sided grid does not necessarily satisfy the Eulerian condition; however, some of the necessary and sucient conditions stated by

Frank in this case are in fact equivalent to the cut condition on some particular subsets of V . One example of such subsets is the set of all vertices lying on the left of any given column c (called a vertical cut ): requiring the cut condition on all such sets of vertices is then equivalent to requiring that the number of rows in the grid is greater than or equal to the congestion of the grid, i.e., the maximum number of pairs having one endpoint on the left of c (included) and one endpoint on the right of c, over all columns c. Such a condition will be called the congestion condition.

The rst step of the approach we proposed in [START_REF] Bentz | Maximum integer multiow and minimum multicut problems in two-sided uniform grid graphs[END_REF] was to prove that determining the maximum number of source-sink pairs (s i , s i ) that can be selected in a two-sided grid so as to satisfy the congestion condition can be done eciently, by solving a linear program having a totally unimodular constraint matrix. Alternatively, it was also observed that this can be done by solving a call control on a chain, a problem that was solved in linear time by Adamy, Ambuehl, Sai Anand and Erlebach [START_REF] Adamy | Call Control in Rings[END_REF].

The second step of this approach was to use Frank's results in order to prove that, in some cases, satisfying the congestion condition is in fact sufcient to simultaneously route all the selected source-sink pairs along edgedisjoint paths, while in any case sacricing at most one of the selected source-sink pairs ensures that all the other selected ones can be simultaneously routed along edge-disjoint paths. The link with a linear program having a totally unimodular constraint matrix, established during the previous step, also allowed us to prove, by means of the Okamura-Seymour theorem, that the dual of this linear program actually models MinMC in this special case. A hole in the proof of one of the main lemmas was later pointed out by Guyslain Naves, but we were able to x it, and to write down the details in a proper erratum [BCR]. We obtained in particular the following result: ]). In any two-sided grid with capacities 1 that does not satisfy the congestion condition and has an odd number of rows, the optimal values of MaxIMF (i.e., MaxEDP) and MinMC are the same, and can be computed in linear time.

Theorem 2.3 ([BCR07, BCR13
The results concerning MaxEDP can be generalized to MaxIMF when all capacities are equal to a common value κ (uniform capacities), provided that the amount of ow routed from s i to s i is not allowed to be greater than κ, by using the pair of linear programs mentioned above, as well as a variant of the Okamura-Seymour theorem that applies to edge-capacitated planar graphs. More precisely, we gave a characterization of the cases where MaxIMF and MinMC have the same optimal value when κ ≥ 2, and showed that, in all other cases, the dierence between these optimal values is 1 (as this was already established when κ = 1). This yields:

Theorem 2.4 ([BCR07]). In any two-sided grid with uniform capacities, the dierence between the optimal values of MaxIMF and MinMC is at most 1, and these optimal values can be computed in polynomial time. Figure 2.1 shows a rectilinear grid with 10 columns, 2 rows, and 10 sourcesink pairs. All the sources s i lie on the uppermost row, and all the sinks s i lie on the lowermost row. For instance, s 2 , s 8 and s 10 lie respectively on the 1st, the 3rd and the 8th column.

The congestion of the whole grid is 4 (the value is reached for c = 4 or c = 6), and the minimum number of source-sink pairs that we have to sacrice in order to satisfy the congestion condition, i.e., in order to obtain a congestion that does not exceed 2, is 2. Moreover, the only way to achieve this is to sacrice (s 3 , s 3 ) and (s 8 , s 8 ), so any of the two linear programs mentioned above has optimal value 10 -2 = 8.

However, in the rectilinear grid obtained in this way, Frank's conditions show that it is not possible to simultaneously route the 8 remaining sourcesink pairs along edge-disjoint paths, and so at least one additional source-sink pair needs to be sacriced. Here, sacricing (s 10 , s 10 ) is sucient to ensure that the 7 remaining source-sink pairs can be simultaneously routed along edge-disjoint paths (these 7 paths are the 7 dotted lines in the gure): thus, MaxEDP has optimal value 7, although MinMC has optimal value 8.

We also proved in [START_REF] Bentz | Maximum integer multiow and minimum multicut problems in two-sided uniform grid graphs[END_REF] that MinMC is NP-hard in rectilinear grids that are not two-sided, even if all sources and sinks lie on the outer face and all capacities are 1. Finally, note that, while nding edge-disjoint paths in planar graphs where any vertex not on the outer face has even degree and where all sources and sinks lie on the outer face can be done eciently thanks to the results that Frank proved in [START_REF] Frank | Edge-disjoint paths in planar graphs[END_REF], which can be seen as a generalization of both the Okamura-Seymour theorem and Frank's previous results concerning rectilinear grids, MaxEDP is APX-hard in this case, as it is APX-hard in 1-outerplanar graphs (also called outerplanar graphs). Actually, as we already mentioned earlier in this section, it is even APX-hard in edge-outerplanar graphs. Therefore, it seems very unlikely that results such as ours can be extended, in some way, to this more general case. Now, we turn our attention towards directed graphs. Indeed, apart from trees, Garg, Vazirani and Yannakakis also studied the use of primal-dual algorithms for variants of MaxIMF and MinMC in directed graphs. In the multiterminal variants of these problems, we are given, in an edge-capacitated graph, a set of terminal vertices T = {t 1 , t 2 , . . . , t |T | } with |T | ≥ 2, and the source-sink pairs are (t i , t j ) for all pairs (i, j) with i = j.

In [START_REF] Garg | Multiway Cuts in Directed and Node Weighted Graphs[END_REF], Garg et al. described a divide-and-conquer primal-dual algorithm that, in any multiterminal instance dened on a directed graph, computes in polynomial time a feasible integral multiow F and a feasible multicut C such that val(C) ≤ 2 log 2 (|T |)•val(F ). Moreover, Costa et al. showed in [START_REF] Costa | Minimal multicut and maximal integer multiow: A survey[END_REF] that, in any multiterminal instance dened on a directed acyclic graph, any optimal integral multiow F and any optimal multicut C satisfy val(F ) = val(C), by reducing MaxIMF and MinMC in this case to classical maximum ow and minimum cut problems, respectively.

In [START_REF] Bentz | The maximum integer multiterminal ow problem[END_REF][START_REF] Bentz | The maximum integer multiterminal ow problem in directed graphs[END_REF], I introduced a new parameter T L ⊆ T for these problems: T L is the set of lonely terminals, which is dened as the set of terminals that lie on at least one directed cycle containing no other terminal. Note that |T L |, the number of lonely terminals, is upper-bounded both by |T | and by the number of directed cycles in the digraph, and that it can be arbitrarily smaller than these two bounds. Thanks to this parameter, I was able to slightly improve the approximation result of Garg et al., as well as to provide some kind of dichotomy results for computing optimal solutions to such problems. The rst result can be stated as follows:

Theorem 2.5 [START_REF] Bentz | The maximum integer multiterminal ow problem in directed graphs[END_REF]). Given any multiterminal instance dened on a arccapacitated digraph, a feasible integral multiow F and a feasible multicut • In all other cases, MaxIMF is APX-hard.

C such that val(C) ≤ 2 log 2 (|T L | + 2) • val(F ) can be computed
Note, in particular, that if the input graph is a directed ring (i.e., a graph consisting only of one directed cycle), then |T L | = 0. However, when switching from multiterminal instances to non multiterminal ones, things are a bit dierent in this case. Directed rings have been studied in [START_REF] Bentz | Multicuts and integral multiows in rings[END_REF],

together with undirected rings (i.e., graphs consisting only of one cycle), since any undirected ring can be transformed into a directed one by directing the edges clockwise, and doubling the number of source-sink pairs. This was not stated explicitly in [START_REF] Bentz | Multicuts and integral multiows in rings[END_REF], but, in a directed ring, the optimal value of MinMC is at most twice the one of the continuous relaxation of (ILP-MC ). Indeed, if there is an optimal multicut consisting of only one arc, then it is easy to see that there exists an optimal solution for Max-IMF where this arc will be saturated, and so the optimal values of MinMC and of the continuous relaxation of (ILP-MC ) will be the same. Otherwise, any optimal multicut contains at least two arcs. By removing the arc having the smallest capacity in such a solution, we are left with a path. It is well-known that, in a path, MinMC and the continuous relaxation of (ILP-MC ) have the same optimal value (which is, by assumption, greater than or

CHAPTER 2. INTEGRAL MULTIFLOWS & MULTICUTS 20

equal to the capacity of the arc that was removed to obtain a path), since the constraint matrix of this linear programming formulation is an interval matrix, and hence is totally unimodular. This concludes our claim.

What was stated and proved explicitly in [START_REF] Bentz | Multicuts and integral multiows in rings[END_REF], however, is the following result about the optimal value of MaxIMF:

Theorem 2.7 [START_REF] Bentz | Multicuts and integral multiows in rings[END_REF]). Let F be a maximum multiow in a directed ring. Then, the optimal value of MaxIMF in this ring is val(F ) .

Moreover, the proof shows that an integral multiow of value val(F ) can be computed eciently by using a linear program with a totally unimodular constraint matrix. We also proved in [START_REF] Bentz | Multicuts and integral multiows in rings[END_REF] that, when all capacities are equal, an optimal integral multiow can be computed in linear time. Since we have val(F ) ≤ 2 val(F ) , the worst case being when val(F ) lies in the interval [1,2[, the previous theorem immediately implies, together with the above discussion, that we have the following result:

Corollary 2.2. In directed rings, the ratio between the optimal values of MinMC and MaxIMF is at most 4.

Note, however, that this may be a rough estimate. The simple example of a directed ring with three vertices a, b, c, three arcs (a, b), (b, c), (c, a) with capacity 1, and three source-sink pairs (a, c), (b, a), (c, b), shows that this ratio can be at least as high as 2. Indeed, in this case, we have val(

F ) = 3 2 ,
val(F ) = 1, and any optimal multicut has value 2 (it consists of two arcs).

Solving MinMC with few source-sink pairs

During my PhD thesis, I studied the complexity and inapproximability of MinMC in directed acyclic graphs, as well as in some generalizations.

Indeed, the related problem of simultaneously routing the maximum number of source-sink pairs (s i , s i ) along arc-disjoint paths in a directed acyclic graph is known to be polynomial-time solvable when the number of source-sink pairs is O(1), while in general digraphs both this problem and MinMC have been proved to be NP-hard even with only two source-sink pairs [START_REF] Fortune | The directed subgraph homeomorphism problem[END_REF][START_REF] Garg | Multiway Cuts in Directed and Node Weighted Graphs[END_REF].

Drawing inspiration from a proof detailed in [START_REF] Cǎlinescu | Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width[END_REF], I proved, by proposing a reduction from 3SAT, that MinMC is NP-hard in directed acyclic graphs, even under very specic restrictions:

Theorem 2.8 [START_REF] Bentz | On the complexity of the multicut problem in bounded tree-width graphs and digraphs[END_REF]). MinMC is NP-hard in directed acyclic graphs, even if all weights are 1, all vertex degrees are at most 3, and the underlying undirected graph is a bipartite cactus.

It was also highlighted that, actually, MinMC in directed acyclic graphs is equivalent to MinMC in layered digraphs, by means of a simple transformation. A layered digraph is a directed graph G = (V, E) whose vertex set can be partitioned into q ≥ 2 sets V 1 , . . . , V q such that, for each arc (u, v), we have u ∈ V i and v ∈ V i+1 for some i ∈ {1, . . . , q -1}. The V i 's will be called layers, and we let p = max i |V i |. The proof of Theorem 2.8 showed that this NP-hardness result still holds if either p = O(1) or q = O(1).

However, if both p and the number of source-sink pairs are O(1), then an ecient dynamic programming algorithm was proposed, yielding:

Theorem 2.9 [START_REF] Bentz | On the complexity of the multicut problem in bounded tree-width graphs and digraphs[END_REF]). In layered digraphs, MinMC is FPT with respect to p = max i |V i | and the number of source-sink pairs.

Actually, the dynamic programming algorithm used in this case even

shows that MinMC becomes linear-time solvable when both p = max i |V i | and the number of source-sink pairs are O(1).

These results raised two types of questions: on the one hand, what can be said about inapproximability results, and, on the other hand, what happens if we bound (only) the number of source-sink pairs? In [START_REF] Bentz | On the complexity of the multicut problem in bounded tree-width graphs and digraphs[END_REF], the former question was answered partially. In order to show how, we rst need to make some comments on directed acyclic graphs and their possible generalizations.

Although the denition of the right notion of tree-width is rather clear in undirected graphs, this is far from being the case in directed graphs.

Actually, several notions have been proposed during the years, and each one shares some properties with its undirected counterpart, but none manages to gather all the nice properties that would be needed [START_REF] Berwanger | The DAG-Width of Directed Graphs[END_REF][START_REF] Hunter | Digraph measures: Kelly decompositions, games, and orderings[END_REF][START_REF] Johnson | Directed Treewidth[END_REF]. This is why it is much harder to compare results related to such widths (in particular, tractability results when some width is small) in directed graphs. However, to the best of our knowledge, all these widths share the fact that the digraphs with the smallest width are exactly the directed acyclic graphs. Hence, proving a hardness result in directed acyclic graphs would allow to prove the same hardness result in all digraphs with bounded width, whatever this width is (provided that it is among the ones that we mentioned).

Unfortunately, there was no result in [START_REF] Bentz | On the complexity of the multicut problem in bounded tree-width graphs and digraphs[END_REF] concerning the inapproximability of MinMC in directed acyclic graphs, but I showed that, when one of these widths is bounded, an APX-hardness result holds: Theorem 2.11 [START_REF] Bentz | On the hardness of nding near-optimal multicuts in directed acyclic graphs[END_REF]). MinMC is APX-hard in directed acyclic graphs, even when there are only two source-sink pairs.

The reduction used to prove this theorem is from the problem Max2SAT (an alternative proof, which works only for three source-sink pairs, uses a reduction from the minimum vertex cover problem), and also shows that this hardness result remains true in layered digraphs where all capacities are 1 and the number of layers q is O(1), hence complementing Theorem 2.9.

It should also be noticed that, up to a constant factor, this result is best possible when the number of source-sink pairs is O(1) (to see this, simply take as a heuristic solution the union over all i of a minimum cut between s i and s i ), and that it matches the best inapproximability result known for MinMC in general digraphs having an arbitrary number of source-sink pairs that is based only on the assumption P =NP. Indeed, there exist slightly stronger inapproximability results for the general case, but to the best of our knowledge they are all based on stronger complexity assumptions [11,[START_REF] Chuzhoy | Hardness of cut problems in directed graphs[END_REF].

Let us now turn to undirected graphs. When there are only two sourcesink pairs (s 1 , s 1 ) and (s 2 , s 2 ), MinMC is known to be tractable. Indeed, it suces to compute two minimum cuts, one separating {s 1 , s 2 } from {s 1 , s 2 }, and the other separating {s 1 , s 2 } from {s 1 , s 2 }: the best solution among these two cuts is an optimal solution for MinMC [START_REF] Yannakakis | Cutting and partitioning a graph after a xed pattern[END_REF]. However, the problem has been shown to be APX-hard when there are three pairs (or more) [START_REF] Dahlhaus | The complexity of multiterminal cuts[END_REF]. So, it is natural to study its complexity in relevant special cases when there are O(1) pairs, as otherwise the problem is APX-hard even in stars [START_REF] Garg | Primal-dual approximation algorithms for integral ow and multicut in trees[END_REF].

In [START_REF] Bentz | On the complexity of the multicut problem in bounded tree-width graphs and digraphs[END_REF], I showed, by using a result of Dahlhaus et al. concerning the multiterminal variant of the problem, that the following result holds:

Theorem 2.12 [START_REF] Bentz | On the complexity of the multicut problem in bounded tree-width graphs and digraphs[END_REF]). When the number of source-sink pairs is O(1),

MinMC is polynomial-time solvable in graphs of bounded tree-width.

The proof relies on a reduction from MinMC to its multiterminal variant, which is polynomial and increases the tree-width of the graph by a constant when the number of source-sink pairs is O(1). (We shall give more details about a variant of this reduction in the next paragraph, as we will need it for subsequent results.) I later discovered that this result has been proved

independently in [START_REF] Guo | Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs[END_REF], using a slightly dierent proof.

I also studied the case of planar graphs. I proved in particular that the case where sources and sinks lie on the outer face can be reduced eciently to a tractable case of the multiterminal variant. Actually, any optimal solution to an instance of MinMC can be seen as a partition of the input graph into connected components such that, for each i, no connected component contains both s i and s i . By linking all the sources and sinks in each connected component to a dedicated terminal, using edges with suciently large capacities, one obtains an instance of the multiterminal variant. If the number of source-sink pairs is O(1), then obviously the number of partitions to enumerate is O(1). When the input graph is planar and all the sources and sinks lie on the outer face, I showed that the partitions that need to be enumerated satisfy some strong properties, which ensure that the multiterminal instances that are generated during the algorithm remain planar.

As the multiterminal variant of MinMC is known to be polynomial-time solvable in planar graphs if the number of terminals is O(1) [START_REF] Dahlhaus | The complexity of multiterminal cuts[END_REF], this yields: Theorem 2.13 [START_REF] Bentz | A simple algorithm for multicuts in planar graphs with outer terminals[END_REF]). When there are O(1) source-sink pairs and all sources and sinks lie on the outer face, MinMC is tractable in planar graphs.

The algorithm used to prove this theorem even shows that, in this case, the problem can be solved in linear time when there are two source-sink pairs. This result left as open the existence of an FPT algorithm for MinMC with respect to the number of source-sink pairs in this case (actually, a very recent proof of mine, which extends ideas already mentioned in [START_REF] Bentz | New results on planar and directed multicuts[END_REF] but is still unpublished, shows that such an algorithm does exist [START_REF] Bentz | An FPT algorithm for planar multicuts with sources and sinks on the outer face[END_REF]), as well as the complexity of MinMC in planar graphs when the number of sourcesink pairs is O(1), a case that was listed as one among ten open questions in my PhD thesis. In order to settle this question, I tried to adapt some of the ecient algorithms that were known for the multiterminal variant of the problem in this case. Among the three algorithms I was aware of, two were based on strong properties linked to the multiterminal nature of the problem at hand: on the one hand, a matroid structure [START_REF] Hartvigsen | The planar multiterminal cut problem[END_REF], and, on the other hand, the fact that, in any optimal solution to a multiterminal instance, any connected component of the associated partition contains only one terminal [START_REF] Dahlhaus | The complexity of multiterminal cuts[END_REF]. Therefore, it seemed unlikely that there was a way to adapt these two ones to the more general case of MinMC.

By studying the third algorithm, due to Yeh [START_REF] Yeh | A simple algorithm for the planar multiway cut problem[END_REF], I nally discovered that its proof was wrong. Roughly speaking, one of the main properties used in this proof stated that, if we enumerate enough vertices, replacing some part of an optimal solution by a minimum cut separating a terminal and the enumerated vertices from the other terminals yields another solution. In my PhD thesis, I provided a counter-example to this statement (see Figure 2.2).

In this multiterminal instance, the ve terminals, t 1 to t 5 , are the big black vertices at the center and in the four corners of the grid, and the only optimal solution is given by the 32 edges crossed by the dashed lines, which all have capacity 1. Any edge incident to t 1 has capacity 2, while any other bold edge has capacity 1. Any edge not mentioned yet has a suciently large capacity. Yeh's algorithm identies the ve big black vertices incident to the bold edges (including t 1 ), and the proof claims that replacing the 28 edges of the current solution not lying on the outer face by a minimum cut separating these ve black vertices from the four other terminals (t 2 to t 5 ) yields a new feasible solution. However, the only such minimum cut is obtained by removing the bold edges (for a total capacity of 24), and these edges clearly do not yield a feasible solution to the considered multiterminal instance, as t 2 is not separated from t j , for each j ∈ {3, 4, 5}, for instance.

This counter-example was also mentioned in [START_REF] Bentz | New results on planar and directed multicuts[END_REF], and later it was proved in [START_REF] Cheung | Revisiting a simple algorithm for the planar multiterminal cut problem[END_REF] that the algorithm itself (and not only its proof ) is not correct. In [START_REF] Bentz | A polynomial-time algorithm for planar multicuts with few source-sink pairs[END_REF], I proposed another ecient algorithm for solving MinMC in this case, based on the geometric notion of homotopic paths. Unfortunately, a hole in the proof of one of the lemmas was found by Éric Colin de Verdière, who later provided his own algorithm to solve MinMC in polynomial time when the graph is planar and the number of source-sink pairs is O(1) [24].

Solving variants of MaxIMF and MinMC

In this section, we describe some algorithmic results concerning problems that can be seen as variants or generalizations of MaxIMF or MinMC.

In the rst variant we shall consider, we are given a list of source-sink pairs in an edge-capacitated rectilinear grid, all capacities being equal to a common integer c ≥ 1. More precisely, we are interested in the case of a so-called dense channel : all sources (resp. sinks) lie on the uppermost (resp. lowermost) row, and the number of source-sink pairs equals the number of columns. Therefore, all vertices on the uppermost (resp. lowermost) row are sources (resp. sinks), and any other vertex is neither a source nor a sink. Such a setting arises, for instance, in the context of VLSI layout: nodes need to be connected together by wires on a rectilinear board, and there is a limit on the number of wires that can be installed in parallel. Moreover, because installing wires is costly, one wants to install wires so that their total length is as small as possible. Formally, we want to link each source to its corresponding sink with a path, while respecting the capacity constraints on the edges, and while minimizing the total length of the paths we use.

When c = 1, this problem amounts to nding edge-disjoint paths linking each source to its corresponding sink, while minimizing the total length of these paths. Frank's results on edge-disjoint paths in rectilinear grids, mentioned in Section 2.2, imply that such edge-disjoint paths cannot exist in a dense channel, except in the very special case where every source-sink pair can be routed along a vertical path. In all other cases, Formann, Wagner and Wagner showed in [START_REF] Formann | Routing through a dense channel with minimum total wire length[END_REF] that, if one adds an additional column on one side (left or right) of the grid, then a routing of minimum total length can be computed in polynomial time, and cannot use shortest paths.

For all other values of c, we proved in [START_REF] Bentz | The shortest multipaths problem in a capacitated dense channel[END_REF] that this problem can be solved in polynomial time, and that, in any optimal solution, any sourcesink pair is routed along a shortest path. Actually, we proved a slightly more general result, extending partial results previously obtained by three of the authors of [START_REF] Bentz | The shortest multipaths problem in a capacitated dense channel[END_REF]: this remains true even if all horizontal edges have the same capacity, and all vertical edges have the same capacity (not necessarily equal to the one of the horizontal edges), provided that at least one of these two capacities is not equal to 1 (otherwise, we are in the case studied by Formann et al.). Summing up, we proved the following result: Theorem 2.14 [START_REF] Bentz | The shortest multipaths problem in a capacitated dense channel[END_REF]). In a dense channel where all horizontal edges have the same capacity, all vertical edges have the same capacity, and not all capacities are equal to 1, one can compute in polynomial time, if it exists, a set of paths linking each source to its corresponding sink, while satisfying all capacity constraints and minimizing the total length of the paths in this set.

Moreover, any path in this set of paths is a shortest path. Now, we shall focus our attention on two generalizations of MinMC.

The rst one consists, in its simplest version, in adding a cardinality constraint (i.e., bounding the number of edges used in a solution) to MinMC.

That is, we add a packing constraint to a covering problem. The results presented here were obtained during the Master's internship that N. Derhy did under the supervision of M.-C. Costa, F. Roupin and myself [START_REF] Derhy | Résolution pratique de problèmes de multicoupes dans les graphes non orientés (in French)[END_REF].

When there is only one source-sink pair, MinMC is simply the minimum cut problem. We proved in [START_REF] Bentz | Cardinality constrained and multicriteria (multi)cut problems[END_REF] that, even in this special case, adding a cardinality constraint makes the problem much harder: Theorem 2.15 [START_REF] Bentz | Cardinality constrained and multicriteria (multi)cut problems[END_REF]). Computing the minimum capacity of a cut that separates a given source from a given sink and uses no more than a given number of edges is a strongly NP-hard problem.

When there is more than one source-sink pair, it is known that MinMC is polynomial-time solvable in directed trees [START_REF] Costa | Minimal multicut and maximal integer multiow: A survey[END_REF], since in particular the constraint matrix of the ILP formulation (ILP-MC ) is totally unimodular. Thanks to a small example, we showed in [START_REF] Bentz | Cardinality constrained and multicriteria (multi)cut problems[END_REF] that adding a cardinality constraint can destroy this property, even in directed stars (i.e., directed graphs whose underlying undirected graph is a star). Actually, we proved that the problem becomes much harder even in this very special case: Theorem 2.16 [START_REF] Bentz | Cardinality constrained and multicriteria (multi)cut problems[END_REF]). The problem obtained by adding a cardinality constraint to MinMC is strongly NP-hard, even in directed stars.

However, in another well-known special case (i.e., paths), we proved that adding a cardinality constraint does not destroy the total unimodularity of the constraint matrix of (ILP-MC ). This implies: Theorem 2.17 [START_REF] Bentz | Cardinality constrained and multicriteria (multi)cut problems[END_REF]). The problem obtained by adding a cardinality constraint to MinMC is polynomial-time solvable in paths.

Actually, we also provided a (combinatorial) polynomial-time dynamic programming algorithm for MinMC with cardinality constraint in this case.

We also noticed in [START_REF] Bentz | Cardinality constrained and multicriteria (multi)cut problems[END_REF] that the problem obtained by adding a cardinality constraint to MinMC can be seen as a special case of a multicriteria multicut problem. Given a set of bounds B 1 , . . . , B ν and a list of source-sink pairs in a graph where each edge e is weighted by a weight vector w(e) of size ν, the multicriteria multicut problem consists in deciding whether there exists a multicut whose total edge weight with respect to the ith components of the weight vectors w is smaller than or equal to B i , for each i ∈ {1, . . . , ν}. When ν = 2 and the second component of each weight vector is 1, the problem amounts to deciding whether there is a multicut using at most B 2 edges, and whose total capacity (given by the rst components of the weight vectors w) is at most B 1 . For this more general problem, we showed: Theorem 2.18 [START_REF] Bentz | Cardinality constrained and multicriteria (multi)cut problems[END_REF]). When weight vectors are arbitrary, the multicriteria multicut problem is NP-complete in paths, in the weak sense if ν = O(1) (even if ν = 2), and in the strong sense otherwise.

The second generalization of MinMC that we shall consider will be called partial MinMC. Consider a MinMC instance, together with an integer p: the problem is then to compute the minimum capacity of a set of edges whose removal leaves no path from s i to s i , for at least p source-sink pairs (s i , s i ).

If p equals the number of source-sink pairs, then this is exactly MinMC.

Moreover, partial MinMC can be seen as a partial covering problem.

A natural question is then: can we exhibit cases where MinMC and partial MinMC do not share the same complexity status? The answer to this question was unknown until D. Chalu and I proved the following result, during the Master's internship he did under my supervision: Theorem 2.19 ([9]). Partial MinMC is strongly NP-hard in directed stars.

Since the full proof of this result is available only in D. Chalu's Master thesis, we provide the main steps here.

First, we show that partial MinMC in directed stars is polynomially equivalent to another partial covering problem, called the Partial Weighted Vertex Cover problem (or PWVC), in bipartite graphs. In this problem, we are given a node-weighted graph, and the goal is to compute the weight of a minimum-weight set of vertices that covers at least a given number of edges.

It is clearly NP-hard in general graphs (as optimally covering all edges is), and we will show that it remains NP-hard in bipartite graphs. Take any instance of partial MinMC in a directed star. We can assume without loss of generality that all sources have out-degree 1 and in-degree 0, and that all sinks have out-degree 0 and in-degree 1. We associate an undirected bipartite graph to this directed star by taking as vertices the sources and sinks (the weight of each vertex being the weight of the arc incident to the corresponding source or sink), and by adding an edge between two vertices if the corresponding source and sink in the directed star belong to the same source-sink pair. Then, in the partial MinMC instance dened in a directed star, removing an arc is clearly equivalent, in the PWVC instance dened in a bipartite graph, to selecting the vertex (source or sink) this arc is incident to. Conversely, any PWVC instance in a bipartite graph can be polynomially reduced to a partial MinMC instance in a directed star, using the same correspondence (edges become source-sink pairs).

It remains to show that PWVC is strongly NP-hard in bipartite graphs. We reduce from the following problem, which was shown to be strongly NPcomplete in [START_REF] Bentz | Cardinality constrained and multicriteria (multi)cut problems[END_REF]: given a connected bipartite graph G with bipartition (L, R) and an integer l ≥ 1, decide whether there exists a vertex cover of G having l vertices in L and r = ν(G) -l vertices in R, where ν(G) is the minimum size of a vertex cover in G. Take any instance of this problem in a graph G with m edges, and link m + 1 ≥ ν(G) pendant vertices to each vertex in L (this yields a new bipartite graph G ). Moreover, in G , set the weight of any vertex to 1 if it belongs to R, and to m + 1 otherwise. Then, it is easy to see that in G there exists a vertex cover of weight at most l(m + 1) + (ν(G) -l) = lm + ν(G) that covers at least m + l(m + 1) edges if and only if in G there exists a vertex cover having l vertices in L and r = ν(G) -l vertices in R. The if part is trivial, and the only if part comes from the fact that taking at least l vertices in L is the only way to cover at least l(m + 1) edges, taking more than l vertices in L would cost at least (l + 1)(m + 1) > lm + ν(G), and covering the m edges of G using l vertices in L (which already cover l(m + 1) edges incident to pendant vertices) and r = ν(G) -l vertices in R is the only way to cover m + l(m + 1) edges in G . This ends the proof of Theorem 2.19.

Although we do not provide all the details here, it was also shown in [START_REF] Chalu | Résolution ecace de problèmes de multicoupes partielles[END_REF] that partial MinMC can be solved in polynomial time in rooted trees, using a dynamic programming algorithm. Therefore, if P =NP, partial MinMC does not have the same complexity status in directed stars and in rooted trees (while MinMC is polynomial-time solvable in both cases, as it is polynomialtime solvable in directed trees).

During the PhD thesis of P. Le Bodic, we further studied the complexity of partial MinMC, and of some related problems. It was shown, in particular, that the partial version of another cut problem does not behave like its non partial counterpart. Assume we are given an integer p and a set of k terminal sets of vertices T 1 , . . . , T k (or clusters ) in a graph. A cluster T i is isolated from a cluster T j if, for each pair of vertices u ∈ T i and v ∈ T j , there is no path from u to v. The partial MinVMCC (for partial minimum vertex multi-cluster cut) problem then consists in computing the minimum number of vertices that need to be removed in order to isolate at least p of the clusters from all the others. On the one hand, it was proved in [START_REF] Bodic | Variantes non standard de problèmes d'optimisation combinatoire[END_REF][START_REF] Bentz | On the complexity of partial colored multiterminal cut problems[END_REF] that: Theorem 2.20 [START_REF] Bodic | Variantes non standard de problèmes d'optimisation combinatoire[END_REF][START_REF] Bentz | On the complexity of partial colored multiterminal cut problems[END_REF]). Partial MinVMCC is NP-hard in the strong sense in undirected trees.

On the other hand, note that the non partial version of MinVMCC (i.e., the case where p = k) can be solved in polynomial time in undirected graphs of bounded tree-width (and hence in undirected trees), by using a dynamic programming algorithm similar to the one mentioned in [START_REF] Dahlhaus | The complexity of multiterminal cuts[END_REF].

Finally, let us mention that a general result regarding (partial) MinMC was proved in [START_REF] Bodic | Variantes non standard de problèmes d'optimisation combinatoire[END_REF][START_REF] Bentz | On the complexity of partial colored multiterminal cut problems[END_REF]. Given a list of source-sink pairs in a graph G, let H denote the graph whose vertex set is composed of the sources and sinks in G, and where there is an edge between two vertices if and only if there exists a source-sink pair they both belong to. Moreover, let G + H denote the graph obtained from G by adding the edges in H (except when such an edge already exists in G), and similarly let G + H denote the graph obtained from G by adding the edges in H, the complement of H (except when such an edge already exists in G). Then, the following holds: Note that this theorem unies and generalizes to partial MinMC two results previously known for MinMC. First, it was noticed in [START_REF] Dahlhaus | The complexity of multiterminal cuts[END_REF] that the multiterminal variant of MinMC can be solved by a polynomial-time dynamic programming algorithm in graphs of bounded tree-width (in this case we have tw(G + H) = O(1), since H is a clique). Second, it was proved in [START_REF] Gottlob | A logical approach to multicut problems[END_REF] that MinMC is polynomial-time solvable when tw(G + H) = O(1), hence generalizing the result of Theorem 2.12. Also note that a simple modication of the APX-hardness proof described in [START_REF] Garg | Primal-dual approximation algorithms for integral ow and multicut in trees[END_REF] for MinMC shows that only requiring that tw(G) + tw(H) = O(1) is not sucient to ensure that (partial) MinMC becomes polynomial-time solvable. Chapter 3 Vertex and edge colorings with cardinality constraints

Introduction

In this chapter, we review results about vertex and edge coloring problems having some sort of additional cardinality constraints.

Coloring problems can be seen as covering problems, as basically they consist in covering the vertices (or edges) of a graph using only some specied type of subgraphs (each vertex, or each edge, must be covered in this way).

The type of subgraphs that will be used depends on the coloring problem that is considered: for instance, recall that the classical vertex coloring problem (also called proper vertex coloring) consists in covering the vertices of a graph using the minimum number (or a given number) of stable sets (each stable set in such a solution being then referred to as a color ).

Adding cardinality constraints to such a problem thus amounts to adding packing constraints to a covering problem. In the next three sections, we will consider three dierent special cases of this general setting. In Section 3.2, we will consider non proper edge coloring problems in complete bipartite graphs, in which we dene a bound on the number of edges of each color incident to each vertex, and also require that the subgraph induced by the edges of each color has a special structure. In Section 3.3, we will consider vertex (and edge) coloring problems in which we are given a set of (not necessarily disjoint) chains in a graph, together with bounds (i.e., cardinality constraints) on the number of vertices (or edges) of each color in each chain, and we look for a coloring (proper or not) satisfying these bounds. Finally, in Section 3.4, we will consider vertex (and edge) colorings when a partition of the vertex set is given, and we look for a proper coloring satisfying given bounds on the number of vertices of each color in each set of the partition.

We will also show that the problems considered in Sections 3.2 and 3.3 generalize the following problem, which was in fact what motivated their study in the rst place. We are given a list of p 1 + p 2 integers h 1 , . . . , h p 1 , v 1 , . . . , v p 2 , and we consider the problem of deciding whether there exists a p 1 × p 2 matrix containing 0's and 1's such that, for each i ∈ {1, . . . , p 1 }, the number of 1's on row i is exactly h i , and, for each j ∈ {1, . . . , p 2 }, the number of 1's on column j is exactly v j . This problem, known as one of the basic problems in discrete tomography, was studied by Ryser, who gave necessary and sucient conditions for such a matrix to exist [START_REF] Ryser | Combinatorial properties of matrices of zeros and ones[END_REF]. It should be noticed that these conditions can be checked in polynomial time. The complexity status of natural generalizations of this problem was open several years ago, so we became interested in them, and started working on characterizing or at least identifying tractable special cases of these generalizations.

The papers to which this chapter is related contain numerous results, and we will not describe them all. We will only highlight and comment those that we consider as the most interesting ones. Any reader interested in having knowledge of other results not presented here can refer to the respective journals where these papers have been published.

Degree-constrained edge colorings of complete (bipartite) graphs

In this section, we consider an edge coloring problem. We are given a complete bipartite graph with bipartition (L, R), three colors, and, for each vertex, the number of edges of each color that must be incident to it.

The problem that we consider, denoted by DC-EdgeCol, then consists in deciding whether there exists an (non necessarily proper) edge coloring with three colors that satises all the degree requirements.

We can assume that these requirements are given as upper bounds, as the sum of the three requirements for each vertex v is exactly its degree in the whole bipartite graph, i.e., |L| if v ∈ R and |R| if v ∈ L. Therefore, these requirements can actually be expressed as packing constraints. Also note that DC-EdgeCol can actually be viewed as the problem of deciding whether there exists a (non necessarily complete) bipartite graph that satises the degree requirements for the colors 1 and 2 (the edges of color 3 being only useful to obtain a complete bipartite graph).

For similar reasons, it is not hard to see that, when there is no edge of color 3 (i.e., there are only two colors), DC-EdgeCol is equivalent to deciding whether there exists a (non necessarily complete) bipartite graph where the degree of each vertex is the number of edges of color 1 that must be incident to it. This problem, in turn, is equivalent to deciding whether there exists a |L| × |R| matrix containing 0's (when there is no edge) and 1's (when there is an edge) such that, for each i ∈ {1, . . . , |L|}, the number of 1's on row i is exactly the degree of the ith vertex in L, and, for each j ∈ {1, . . . , |R|}, the number of 1's on column j is exactly the degree of the CHAPTER 3. COLORINGS WITH CARDINALITY CONSTRAINTS 33 jth vertex in R. That is, it is equivalent to the basic problem solved by Ryser in [START_REF] Ryser | Combinatorial properties of matrices of zeros and ones[END_REF]. However, when there are three colors (and not two) in a complete bipartite graph, the complexity status of the problem remained open for a long time (more details on this case are given below).

When we became interested in DC-EdgeCol due to its equivalence with this open problem in discrete tomography, we wanted to identify additional (graph) requirements that could make the problem easier, or harder. For instance, imposing a special structure or condition on the subgraph induced by the edges of color 1, by the ones of color 2, or by the ones of color 1 or 2, may precisely lead to either easier or harder problems.

In the remaining of this section, instead of considering three colors in a complete bipartite graph, we will consider two colors in the bipartite graph (to be determined) obtained by removing the edges of color 3. Moreover, we shall also consider the problem DC-EdgeCol in complete graphs (and not complete bipartite anymore) with three colors: let us refer to this variant as DC-Complete-EdgeCol. Again, instead of reasoning directly on a complete graph with three colors, we will consider two colors in the graph (to be determined) obtained by removing the edges of color 3.

We rst established a link between the hardness of both problems: Theorem 3.1 ([BCP + 09]). DC-Complete-EdgeCol is at least as hard as DC-EdgeCol, as the latter can be reduced to the former.

As DC-EdgeCol is known to be NP-complete since 2012 [START_REF] Dürr | Reconstructing 3-Colored Grids from Horizontal and Vertical Projections is NP-Hard: A Solution to the 2-Atom Problem in Discrete Tomography[END_REF] (before this paper, only the variant with four or more colors was known to be intractable [START_REF] Chrobak | Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms[END_REF]), so is DC-Complete-EdgeCol.

We also proposed a sucient condition for an instance of DC-EdgeCol or DC-Complete-EdgeCol to have a solution: more precisely, if the number of edges of color 1 or 2 is not smaller than some lower bound that we computed, then there always exists a solution (complete bipartite graph with three colors). Then, we studied DC-Complete-EdgeCol and DC-EdgeCol under the assumption that the subgraph induced by the edges of color 1 or 2 has a special structure, and provided necessary and sucient conditions for a solution to exist. Note that all these conditions can be checked in polynomial time. More precisely, we have proved: Theorem 3.2 ([BCP + 09]). When we require that the graph induced by the edges of color 1 or 2 must be a tree, there exist necessary and sucient conditions, which can all be checked in polynomial time, for an instance of DC-EdgeCol or DC-Complete-EdgeCol to have a solution.

This theorem is essentially proved with the help of two key lemmas, called the recoloring and recycling lemmas. The recoloring lemma states that we can merge two connected components of the subgraph induced by the edges of color 1 or 2 into a single connected component, provided that each of these CHAPTER 3. COLORINGS WITH CARDINALITY CONSTRAINTS 34 connected components contains one edge of a given color (1 or 2), and at least one of these two edges lies on a cycle. The recycling lemma basically states that, under some weak assumptions, an edge not lying on a cycle can be put on a cycle, without modifying the number of connected components.

In the proof of Theorem 3.2, we apply the recoloring lemma while we can (decreasing by one the number of connected components each time we use it). Then, we show that the recycling lemma can be used, and use it. After that, the recoloring lemma can be used again, which concludes the proof.

The next result deals with disjoint chains covering the whole graph: Theorem 3.3 ([BCP + 09]). When we require that the graph induced by the edges of color 1 or 2 must be a set of vertex-disjoint chains spanning all vertices, there are necessary and sucient conditions, which can all be checked in polynomial time, for an instance of DC-EdgeCol to have a solution.

For DC-Complete-EdgeCol, we can even require that the edges of color 1 or 2 induce a hamiltonian cycle (i.e., simple and spanning all vertices): Theorem 3.4 ([BCP + 09]). When we require that the edges of color 1 or 2 must induce a hamiltonian cycle, the following conditions are necessary and sucient for an instance of DC-Complete-EdgeCol to have a solution:

• the number of edges of color 1 or 2 incident to each vertex is two,

• there is a vertex incident to an edge of color 1 and to one of color 2.

These conditions can be checked in polynomial time and are clearly necessary (the second one being necessary for a connected solution to exist). The suciency comes from the recoloring lemma: the only case where this lemma cannot be applied is when the edges of color 1 or 2 induce two monochromatic vertex-disjoint cycles, but this is impossible from the second condition. Now we turn to the case where both the edges of color 1 and the edges of color 2 must have a special structure. We rst study hamiltonian chains: Theorem 3.5 ([BCP + 09]). When we require that the edges of each color (1 and 2) must induce a hamiltonian chain, there exist necessary and sucient conditions, which can all be checked in polynomial time, for an instance of DC-EdgeCol or DC-Complete-EdgeCol to have a solution.

Then, we study the case of cycles: Theorem 3.6 ([BCP + 09]). When we require that the edges of each color (1 and 2) must induce a cycle, the following conditions are necessary and sucient for an instance of DC-EdgeCol to have a solution:

• the edges of each color (1 and 2) induce a set of disjoint cycles,

• we have neither the forbidden conguration given in Figure 3.1, nor the one obtained by exchanging edges of color 1 and edges of color 2. In [START_REF] Costa | Using graphs for some discrete tomography problems[END_REF], the rst condition of Theorem 3.6 is shown to be equivalent to a set of necessary and sucient conditions, which can be checked in polynomial time, corresponding to a set of pathological cases that must be forbidden.

Finally, DC-Complete-EdgeCol behaves in a similar way in this case, although the associated necessary and sucient conditions are a bit simpler:

Theorem 3.7 ([BCP + 09]). When we require that the edges of each color (1 and 2) must induce a cycle, there exist necessary and sucient conditions, which can all be checked in polynomial time, for an instance of DC-Complete-EdgeCol to have a solution.

Colorings with cardinality constraints on a given set of chains

In this section, we consider the following problem Col-CC: we are given a list of colors, a graph, and a list of (not necessarily disjoint) chains in this graph, together with the number of vertices of each color that each chain must contain, and we are thus looking for a (not necessarily proper) vertex coloring such that each chain given in the input contains the right number of vertices of each color. Note that these numbers of vertices can as well be given as upper bounds in the input since, for each chain, the sum of these numbers is exactly the total number of vertices on the chain (so, each of these numbers must be reached anyway in any feasible coloring). This way, we can dene these constraints as packing (or cardinality) constraints.

Assume for instance that we are given a rectilinear grid with p 1 rows and p 2 columns, and two colors. For each i ∈ {1, . . . , p 1 }, the ith row (one of the chains given in the input) must contain h i vertices of color 1 and p 2 -h i vertices of color 2. Similarly, for each j ∈ {1, . . . , p 2 }, the jth column (one of the chains given in the input) must contain v j vertices of color 1 and p 1 -v j vertices of color 2. Then, nding a (non proper) coloring CHAPTER 3. COLORINGS WITH CARDINALITY CONSTRAINTS 36 satisfying the cardinality constraints on the p 1 + p 2 chains in this special case is equivalent to nding a p 1 × p 2 matrix containing 0's (corresponding to vertices of color 2) and 1's (corresponding to vertices of color 1) such that, for each i ∈ {1, . . . , p 1 }, the number of 1's on row i is exactly h i , and, for each j ∈ {1, . . . , p 2 }, the number of 1's on column j is exactly v j .

In the above special case, which is Ryser's problem [START_REF] Ryser | Combinatorial properties of matrices of zeros and ones[END_REF], the input graph is a rectilinear grid, and the number of colors is two. When there are four (or more) colors, the problem is known to be NP-complete (even in rectilinear grids where the set of chains is as above), as the corresponding problem in discrete tomography (reconstructing a matrix with four colors, knowing the number of times each color appears in each row and each column) is [START_REF] Chrobak | Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms[END_REF].

However, the complexity of the problem remained open in other special cases (for instance, in other families of bipartite graphs), or when there are three colors. We studied the former question, and the latter one was settled in 2012 (the problem being actually NP-complete) by Dürr et al. [START_REF] Dürr | Reconstructing 3-Colored Grids from Horizontal and Vertical Projections is NP-Hard: A Solution to the 2-Atom Problem in Discrete Tomography[END_REF].

The rst noticeable result that we obtained in [BCdW

+ 08] concerning
Col-CC is the following negative one: Theorem 3.8 ([BCdW + 08]). Col-CC is NP-complete in trees with maximum degree three, even when there are only two colors.

The proof is made by reduction from the NP-complete problem 1-in-3SAT with no negated literal (also called Monotone1-in-3SAT), a variant of 3SAT where each clause must contain exactly one true literal, and which will be described formally in the next section. Informally, in any instance of this problem, we have a set of variables and a set of clauses of size 3 dened on these variables (with only positive literals), and the idea of the reduction is to associate a leaf to each variable and a gadget to each clause. Then, we dene chains in each clause gadget in order to ensure that each such gadget has only 3 possible colorings: for each of these 3 colorings, exactly one of the 3 associated variable leaves has color 1. Having color 1 can thus be associated with being true in a truth assignment, and we prove the equivalence between the solutions to the Col-CC and 1-in-3SAT instances in this way.

However, restricting the way the chains given in the input can interact with each other makes the problem easier when there are two colors: Theorem 3.9 ([BCdW + 08]). When there are two colors, Col-CC can be solved in polynomial time when any chain given in the input has at most two vertices in common with other chains given in the input.

Imposing strong restrictions on the lengths of the chains given in the input also makes the problem easier: Theorem 3.10 ([BCdW + 08]). Col-CC can be solved in polynomial time when any chain given in the input contains at most two vertices.

CHAPTER 3. COLORINGS WITH CARDINALITY CONSTRAINTS 37 It was also proved in [BCdW

+ 08] that the problem becomes NP-complete if chains containing 3 (or more) vertices are allowed, even with only 3 colors.

When the graph is a tree and the chains given in the input are almost disjoint, a rather intricate algorithm, called the Forced and Forbidden Colors procedure, and based on several non trivial properties, can be used to show: Theorem 3.11 ([BCdW + 08]). Col-CC can be solved in polynomial time in trees when any two chains given in the input share at most one vertex.

When we impose in addition that any solution must be a proper coloring, the problem (which is trivial with two colors) becomes a bit harder to deal with. However, one can show the following (positive) result: Theorem 3.12 ([BCdW + 08]). When any solution is required to be a proper coloring, Col-CC can be solved in polynomial time in trees when any two chains given in the input share at most one common vertex.

A reduction inspired by the one used to prove Theorem 3.8 yields: Theorem 3.13 ([BCdW + 08]). When any solution is required to be a proper coloring, Col-CC is NP-complete in trees with maximum degree three, even when there are only three colors.

Finally, if we consider the case of (non necessarily proper) edge colorings, then we impose the number of edges of each color that each chain given in the input must contain. In this case, the complexity of the problem (denoted by EdgeCol-CC) is open in trees, but we were able to prove that the problem is hard in graphs that are hardly more general than trees: Theorem 3.14 ([BCdW + 08]). EdgeCol-CC is NP-complete in cacti with maximum degree three and no cycle of length four or more, even when there are only two colors.

Colorings with local cardinality constraints on a xed partition

In this section, we consider the following problem Col-LocalBounds:

we are given a list of k colors, a graph G = (V, E), a partition (V 1 , V 2 , . . . , V p ) of the vertex set V , and a list of p•k bounds n 11 , . . . , n 1k , . . . , n p1 , . . . , n pk such that k j=1 n ij = |V i | for each i, and we want to decide whether there exists a proper coloring such that, for each i ∈ {1, . . . , p} and for each j ∈ {1, . . . , k}, the number of vertices of color j in V i is n ij . Again, note that, because of the condition k j=1 n ij = |V i | for each i, the numbers n ij can as well be given as upper bounds in the input. This way, we can, as in the previous section, dene these constraints as packing (or cardinality) constraints.

CHAPTER 3. COLORINGS WITH CARDINALITY CONSTRAINTS 38

When p = 1, the problem is known as the Capacitated Coloring problem (see [START_REF] Bonomo | Bounded coloring of cocomparability graphs and the pickup and delivery tour combination problem[END_REF]): Gravier et al. showed that this problem is polynomial-time solvable in graphs of bounded tree-width when the number of colors k is O(1) [START_REF] Gravier | Complexity of list coloring problems with a xed total number of colors[END_REF].

Other very well-known special cases of Capacitated Coloring also include the Equitable Coloring problem (where the sizes of any pair of color classes must dier by at most 1), and the Bounded Coloring problem (where all the bounds n ij are equal), for which numerous results are known (see in particular [START_REF] Bodlaender | Equitable colorings of bounded treewidth graphs[END_REF][START_REF] Bonomo | Bounded coloring of cocomparability graphs and the pickup and delivery tour combination problem[END_REF][START_REF] Gravier | Complexity of list coloring problems with a xed total number of colors[END_REF], as well as additional links referenced in these papers).

In [START_REF] Bentz | Locally bounded kcolorings of trees[END_REF], we proved the following result, with the help of a dynamic programming algorithm: Applications of Col-LocalBounds, and in particular links with scheduling problems, were also discussed in this paper.

Later, I continued working on a generalization of Col-LocalBounds, named WeightedListCol-LocalBounds. In this more general problem, any vertex v has a weight w(v) and a list of possible colors L(v), and the p • k bounds are denoted by W 11 , . . . , W 1k , . . . , W p1 , . . . , W pk , and are such that k j=1 W ij = v∈V i w(v) for each i. The problem consists in deciding whether there exists a proper coloring such that, for each i and for each j, the total weight of the vertices of color j in V i is W ij , and which is a valid list-coloring, i.e., the color of any vertex v in this coloring belongs to L(v).

For this problem, the following set of (unpublished) results can be shown: Theorem 3.16. When both p and the number of colors k are O(1), we can solve WeightedListCol-LocalBounds in pseudo-polynomial time in graphs of bounded tree-width. If, in addition, all vertex weights are bounded by a polynomial in the input size, then we can solve it in polynomial time.

Proof. In order to design a dynamic programming algorithm that solves WeightedLocallyBoundedListColoring in an ecient way provided that a tree decomposition {X i |i ∈ I}, T of the input graph G having minimum width tw(G) is given, let us dene the following function f :

• f (i, c i , ω 11 , . . . , ω 1k , . . . , ω p1 , . . . , ω pk ) = true if there is a list-coloring of G[T i ] where each vertex u ∈ X i has color c i (u) and the total weight of vertices of G[T i ] having color c in V h is ω hc , and false otherwise.

To describe the algorithm, one now simply needs to write down the induction equations dening the values of f (•), for each type of nodes of T : forget, introduce, join and leaf (see Section 1.3). Then, these values will be computed in a bottom-up fashion, starting from the leaves of T .

Note that, by the denition of tree decompositions, any two vertices linked by an edge in G must both belong to at least one common bag of the CHAPTER 3. COLORINGS WITH CARDINALITY CONSTRAINTS 39 tree decomposition (Condition ( 2)). This implies that a (list-)coloring that is proper in each bag is also proper in the whole graph G, provided that each vertex has the same color in each bag it belongs to. Moreover, Condition [START_REF] Bazgan | The most vital nodes with respect to independent set and vertex cover[END_REF] ensures that the subgraph of T induced by the bags any given vertex belongs to is connected, and hence in all these bags this vertex will have the same color if we do not change its color whenever we move (in T ) from one bag to an adjacent one. Therefore, in order to show that a vertex list-coloring is proper in T i , it suces to ensure that it is a proper list-coloring in X i , and that the color of any vertex remains the same when moving from one bag of T i to an adjacent one. Here are the equations computing the values of f (•):

If i is a forget node. Let j denote its child such that X j = X i ∪ {v}:

f (i, c i , ω 11 , . . . , ω pk ) = c j :(c j (u)=c i (u) ∀u∈X i )∧(c j (v)∈L(v))
f (j, c j , ω 11 , . . . , ω pk )

Proof. Each vertex must keep its color when moving from X j to X i .

If i is an introduce node. Let j denote its child such that X j = X i \ {v}, and assume that v ∈ V h :

f (i, c i , ω 11 , . . . , ω pk ) = E f (j, c j , ω 11 , . . . , ω hc i (v) -w(v), . . . , ω pk ) where E = (c i (v) ∈ L(v)) (c i (v) = c i (u) ∀u : uv ∈ Y i ) (c j (u) = c i (u) ∀u ∈ X j ) (ω hc i (v) ≥ w(v)).
Proof. The conditions c i (v) ∈ L(v) and c i (v) = c i (u) ensure that the listcoloring is valid in the subgraph of G induced by X i .

If i is a join node. Let j and l denote its two children, and let w i hc be the total weight of vertices v ∈ X i ∩ V h such that c i (v) = c, for each h and c. f (i, c i , ω 11 , . . . , ω pk ) = (q 11 ,...,q pk )∈Q i f (j, c i , ω 11 + w i 11 -q 11 , . . . , ω pk + w i pk -q pk ) ∧ f (l, c i , q 11 , . . . , q pk ) where Q i = {(q 11 , . . . , q pk ) : w i hc ≤ q hc ≤ ω hc ∀h ∀c}.

Proof. We try all the possible combinations of vertex weights between the two children of node i, and take into account the fact that the weights of the vertices in X i must be counted both in T j and in T l .

If i is a leaf node. In this case, we just have to check that the coloring function c i provides a valid locally bounded list-coloring of G[X i ].

f (i, c i , ω 11 , . . . , ω pk ) = E (w({v ∈ X i ∩ V h : c i (v) = c}) = ω hc ∀h ∀c) where E = (c i (v) ∈ L(v) ∀v ∈ X i ) (c i (v) = c i (u) ∀u, v ∈ X i : uv ∈ Y i ).

CHAPTER 3. COLORINGS WITH CARDINALITY CONSTRAINTS 40

Root value. The value computed at the root r of T is:

cr:cr(u)∈L(u) ∀u∈Xr f (r, c r , W 11 , . . . , W pk )
We conclude the proof by noticing that the overall running time we obtain is O(n(max h,c W hc ) pk k tw(G)+1 ((max h,c W hc ) pk + tw(G)(tw(G) + pk))).

Note that Theorem 3.16 generalizes both Theorem 3.15 (where w(v) = 1 for each vertex v, the tree-width is 1, and any vertex can take any color) and the results in [START_REF] Gravier | Complexity of list coloring problems with a xed total number of colors[END_REF]. This theorem can also easily be extended to the case where one wants to properly color edges instead of vertices.

Furthermore, if the tree-width of the input graph is arbitrary, then Col-LocalBounds is NP-complete (even if k = 3 and p = 1), as the basic problem of deciding whether a graph can be colored with 3 colors is.

Actually, one can show that the conditions p = O(1) and k = O(1) are necessary in Theorem 3.16, since otherwise the problem is strongly NPcomplete, and that the problem is weakly NP-complete even if they hold.

Assume that the vertex weights are arbitrary, and set k = 2 and p = 1.

Take any instance I of the weakly NP-complete Partition problem, where we are given n+1 positive integers a 1 , . . . , a n , B such that n i=1 a i = 2B, and we want to decide whether there exists I ⊂ {1, . . . , n} such that i∈I a i = B. Consider a set of n isolated vertices v 1 , . . . , v n (a graph with tree-width 0) that can take any color, and dene W 11 = W 12 = B, as well as w(v i ) = a i for each i. Then, the answer to instance I is yes if and only if the answer to this instance of WeightedListCol-LocalBounds is yes. This implies that WeightedListCol-LocalBounds is weakly NP-complete in this case.

Assume now that the number of colors k is arbitrary. Bodlaender and Fomin have shown that deciding whether there exists an equitable coloring with k colors when some vertices are already colored is strongly NP-complete in trees [START_REF] Bodlaender | Equitable colorings of bounded treewidth graphs[END_REF]. However, ensuring that a vertex v takes color c can be done by imposing that the list of possible colors for v contains only c. Hence, WeightedListCol-LocalBounds generalizes this problem, and is also strongly NP-complete in trees, even if w(v) = 1 for each vertex v and p = 1.

Finally, assume that p is arbitrary. In this case, it can be shown that WeightedListCol-LocalBounds remains strongly NP-complete, by using a reduction from the following well-known NP-complete problem, which is mentioned in the previous section, but which we now describe formally [START_REF] Garey | Computers and Intractability: a Guide to the Theory of NP-completeness[END_REF]:

Monotone1-in-3SAT

Instance : A set X of ν boolean variables x 1 , . . . , x ν , and a set of µ clauses, each one containing exactly three (non negated) boolean variables from X.

Question : Decide whether there exists a truth assignment for the variables in X such that in every clause there is exactly one variable equal to true.

CHAPTER 3. COLORINGS WITH CARDINALITY CONSTRAINTS 41

More precisely, the following result holds: Theorem 3.17. WeightedListCol-LocalBounds is NP-complete in the strong sense in forests, even if k = 2 and w(v) = 1 for each v ∈ V .

Proof. Given an instance of Monotone1-in-3SAT, we construct an instance of WeightedListCol-LocalBounds as follows: the graph G consists of ν vertex-disjoint stars, one star per variable x i . We denote by v i the central vertex of the ith star, and by u 0 i , . . . , u occ(i) i its leaves, where occ(i) is the number of occurrences of x i in the set of clauses. Then, we dene k = 2, p = ν + µ, and, for each vertex v, w(v) = 1. Moreover, any vertex can take any color. The partition of the vertices of G and their target weights are given by: V h = {v h , u 0 h } and W h1 = W h2 = 1 for each h ∈ {1, . . . , ν}, and V h = {u a i , u b j , u c k }, W h1 = 1 and W h2 = 2 for each h ∈ {ν + 1, . . . , ν + µ}, where we consider that the (h -ν)th clause consists of the ath occurrence of the variable x i , of the bth occurrence of the variable x j , and of the cth occurrence of the variable x k .

It is easy to check that we have the following equivalence between this WeightedListCol-LocalBounds instance and the initial Monotone1in-3SAT instance: for each i ∈ {1, . . . , ν}, variable x i is equal to true if and only if v i has color 2, which concludes the proof.

Complementary results for this problem in other classes of graphs (such as cographs and split graphs) have been obtained recently, but will not be discussed here; the interested reader can refer to [START_REF] Bentz | Weighted and locally bounded list-colorings in split graphs, cographs, and partial k-trees[END_REF]. Chapter 4 Blockers and d-transversals in graphs

Introduction

In this chapter, we review results about minimum d-transversals for several graph problems. Formally, given a weighted graph G, an integer d, and a graph parameter π(G) that cannot increase under vertex (resp. edge) deletions and that is equal to the optimal weight of a set of vertices (resp. edges) satisfying a given graph property Π, a d-transversal for π(G) is a set of vertices (resp. edges) that intersects at least d times any set of vertices (resp. edges) of weight π(G) satisfying property Π in G. A related notion is the following: a blocker for a graph parameter π(G) as dened previously is a set B of vertices (resp. edges) such that π(G -B) < π(G), where G -B is the graph obtained from G by removing the vertices (resp. edges) in B [START_REF] Costa | Minimum d-blockers and d-transversals in graphs[END_REF].

In fact, it is not hard to see that we have the following equivalence: Proposition 4.1 ([ZRP + 09]). Given a weighted graph G and a graph parameter π(G) that cannot increase under vertex (resp. edge) deletions and that is equal to the optimal weight of a set of vertices (resp. edges) satisfying a given graph property, a set of vertices (resp. edges) is a 1-transversal for π(G) if and only if it is a blocker for π(G).

Examples of graph parameters that we shall consider are α(G), the stability number of G, where the property Π consists in being a stable set, and ν(G), the maximum size of a matching in G (which can be eciently computed), the property Π then consisting in being a matching. The general problem that we shall study consists in determining the minimum size (or cost, if each vertex or edge also has a cost) of a d-transversal or blocker. Proposition 4.1 shows that d-transversals can be seen as generalizations of blockers: other generalizations or variants of blockers for dierent graph parameters were considered in [START_REF] Bazgan | The most vital nodes with respect to independent set and vertex cover[END_REF][START_REF] Costa | Minimum d-blockers and d-transversals in graphs[END_REF][START_REF] Zenklusen | Matching interdiction[END_REF], but will not be discussed here.

CHAPTER 4. BLOCKERS AND D-TRANSVERSALS IN GRAPHS 44

Note that, basically, such a problem is hard in two ways: rst, computing the value of π(G) may be hard (this is the case, for instance, for π(G) = α(G) in general graphs); second, even if π(G) can be computed eciently, there may be a huge number of optimal vertex (or edge) sets satisfying the property Π. In particular, proving that the decision version of such a problem belongs to NP (or not) may be a hard task. In the case of blockers (i.e., d = 1), this fact may remain hard to prove whenever computing π(G) is NP-hard, but the decision version of the problem is obviously in NP otherwise.

In any case, this clearly denes a family of covering problems, as one wants to cover at least d times, in an optimal way, any set of vertices (resp. edges) of weight π(G) satisfying property Π in G.

Minimum d-transversals for matchings

This section reviews results about the case where the property Π consists in being a matching, and all edge weights are 1. In other words, one wants to determine the minimum size of a set of edges intersecting at least d times any maximum matching of a graph G, for d ≤ ν(G). The proof is divided into two parts. First, as a direct consequence of Hall's Theorem, we know that such a graph G contains ∆ disjoint perfect (and hence maximum) matchings, meaning that any d-transversal must contain at least d∆ edges. Second, as any vertex is incident to an edge of any perfect matching, taking all the edges incident to the vertices of any independent set of size d indeed yields a d-transversal of size d∆.

We also provided a family of instances showing that, in this case, there may exist minimum-size d-transversals that are not obtained as in Theorem 4.3. A natural way of obtaining bipartite graphs that are not regular (but not by far) is by considering the rectilinear grids. We studied them in [RBP

+ 10],
and proved that the structure of minimum-size d-transversals can be very dierent from the one described in Theorem 4.3.

We shall deal with three dierent main cases, establishing closed formulas for each one of them, before concluding:

• The numbers of rows and columns are even,

• The numbers of rows and columns are odd,

• The number of rows is even and the number of columns is odd.

The following lemma deals with the rst main case: • has size 2d for d = 1 or d = 2.

• has size 3d -2 for d ∈ {3, . . . , ν(G m,n )}.

2. (when m ≥ 4 and n ≥ 4)

• has size 2d for d ∈ {1, 2, 3, 4}.

• has size 3d -4 for d ∈ {5, . . . , m + n -4} and max{m, n} > 4.

• has size 4d -m -n for d ∈ {m + n -3, . . . , ν(G m,n )}.
The construction associated with each of these ve cases is also given explicitly, and the solutions obtained mainly consist in taking all the edges incident to a particular set of vertices, as in Theorem 4.3.

We now turn to the second main case: • has size 2d for d ∈ {1, . . . , ν(G m,n )}.

2. (when m ≥ 3 and n ≥ 3)

• has size 3 for d = 1.

• has size 2d + 2 for d = 2 or d = 3.

• has size 12 for d = 4 and m = n = 3.

• has size 3d -1 for d ∈ {4, . . . , m + n -3} and max{m, n} > 3.

• has size 4d -m -n + 2 for d ∈ {m + n -2, . . . , ν(G m,n )}.
Again, the construction associated with each of these six cases is also given explicitly, and the solutions obtained mainly consist in taking all the edges incident to a particular set of vertices, as in Theorem 4.3.

Finally, we deal with the third main case: • has size 3d -2 for d ∈ {3, . . . , n = ν(G 2,n )}.

3. (when m ≥ 4 and n = 3)

• has size 2d for d ∈ {1, . . . , m 2 + 2}. • has size 3d -m 2 -2 for d ∈ { m 2 + 3, . . . , m}. • has size 5d -5m 2 -3 for d ∈ {m + 1, . . . , 3m 2 = ν(G m,3 )}.
4. (when m ≥ 4 and n ≥ 5)

• has size 2d for d ∈ {1, 2, 3, 4}.

• has size 3d -4 for d ∈ {5, . . . , m + n -3}.

• has size 4d-m-n-1-d-(m+n-3) n-3 2 for d ∈ {m+n-2, . . . , mn 4 + m 4 + n-5 2 }. • has size 4d-m-n- mn 2 -d n-1 2 for d ∈ { mn 4 + m 4 + n-3 2 , . . . , ν(G m,n )}.
As in the two previous lemmas, the construction associated with each case is given, but this time the solutions obtained make use of special structures called dancats (for dancing caterpillars ), shown in Figure 4.2: Unlike the bipartite graphs that were considered above, the last family of bipartite graphs that we studied has arbitrary maximum degree, but no cycles. In other words, we studied trees, and, using a rather intricate dynamic programming approach, we obtained the following result: More precisely, the algorithm used to prove Theorem 4.5 runs in O(n 5 ) time in any tree with n vertices. Later, Zenklusen even managed to solve this problem in polynomial time in graphs of bounded tree-width [START_REF] Zenklusen | Matching interdiction[END_REF].

One last result concerns the minimum size of a d-transversal for ν(G) in non bipartite graphs, and more precisely in complete graphs: Theorem 4.6 ([ZRP + 09]). Let n and d ≥ 1 be two integers such that 2d ≤ n, and let r = n 2 -d. Let us denote by K n the complete graph on n vertices. The minimum size of a d-transversal for ν(K n ) is then:

• n 2 -2r+1 2 if d ≤ n 2 -2 5 n + 3 5
, and a d-transversal of this size can then be obtained by taking all the edges incident to n -2r -1 vertices.

• n-r 2 if d ≥ n 2 -2 5 n + 3 5
, and a d-transversal of this size can then be obtained by taking a clique on n -r vertices.

The proof of this theorem is a bit technical, and shows that the constructions described in the theorem are actually the only ones that can lead to minimum-size d-transversals. This implies, in particular, that the case d = n 2 -2 5 n + 3 5 is the only one where K n contains two (and exactly two) non-isomorphic minimum-size d-transversals. For instance, when n = 4 and d = 1, a minimum-size 1-transversal (or equivalently, from Proposition 4.1, a minimum-size blocker) has size 3, and can be obtained either by taking a triangle, i.e., a clique on 3 vertices (leaving only a claw in the remaining graph), or by taking a claw corresponding to the 3 edges incident to an arbitrary vertex (leaving only a triangle in the remaining graph).

Minimum d-transversals for stable sets

This section reviews results about the case where the property Π consists in being a stable set. In other words, given a graph G where each vertex has both a cost and a weight, one wants to determine the minimum cost (or size, if all costs are 1) of a set of vertices intersecting at least d times any maximum-weight stable set of G, for some d ≥ 1.

CHAPTER 4. BLOCKERS AND D-TRANSVERSALS IN GRAPHS 49

Note that the maximum value that d can take is α(G) if all weights are 1, whereas it is equal to the minimum size of a maximum-weight stable set otherwise: both this value and α(G) may be hard to determine. However, we shall study the problem in bipartite graphs, and in this case α(G) can be computed in polynomial time. Also note that Theorem 4.2 implies that, for any xed d ≥ 1, determining the minimum size of a d-transversal for α(G) is NP-hard in line graphs of bipartite graphs (as a matching in any graph corresponds to a stable set in the associated line graph).

In [BCP

+ 12], we showed the following theorem: Theorem 4.7 ([BCP + 12]). Given a bipartite graph G where each vertex has both a cost and a weight, a minimum-cost set of vertices intersecting at least d times any maximum-weight stable set of G can be found in polynomial time, for any possible value of d ≥ 1.

As this result is based on strong properties of maximum-weight stable sets in bipartite graphs, which can be of independent interest, we describe the main steps of the proof, without providing all the details. In the remainder of the section, let G be a bipartite graph where each vertex v has a cost c(v) and a weight w(v), and let (L, R) be its bipartition and E its edge set.

The rst step consists in partitioning G into three sets of vertices:

• The forced vertices, which belong to all maximum-weight stable sets,

• The excluded vertices, which belong to no maximum-weight stable set,

• The other vertices of G, called free vertices.

Note that any excluded vertex can be removed from G, as it belongs neither to a maximum-weight stable set nor to an optimal d-transversal for α(G). Moreover, such a partition can be computed in polynomial time, as the maximum weight of a stable set in a bipartite graph (either G or a graph obtained from G by removing some vertex) can be determined by computing a maximum ow in an associated directed graph. To see this, orient the edges of G from L to R, and assign to each such arc an innite capacity. Then, add two vertices s and s , an arc of capacity w(v) from s to any vertex v in L, and an arc of capacity w(v) from any vertex v in R to s . Clearly, the value of a maximum ow from s to s in this directed graph G equals, in G, the total weight of vertices minus the maximum weight of a stable set. Also note that a forced vertex does not necessarily belong to a minimumcost d-transversal for α(G), as its cost can be prohibitive. However, we can remove it from G for now, as we shall show later how to deal with it. Hence, we can assume, without loss of generality, that all vertices of G are free, which implies that L and R are two disjoint maximum-weight stable sets.

CHAPTER 4. BLOCKERS AND D-TRANSVERSALS IN GRAPHS 50

The second step consists in identifying forbidden arcs in G , i.e., arcs that carry no ow unit in any maximum ow from s to s . In particular, we show that these arcs can be identied in polynomial time, and that, when G is connected and there are no such arcs in G , L and R are the only maximum-weight stable sets in G.

Therefore, we dene a (unique) partition of G in the following way: we remove from G all the edges associated with the forbidden arcs of G , and denote by G 1 , . . . , G h the h connected components of the resulting graph. Then, it is clear that, for each i, the only two maximum-weight stable sets in G i are obtained by taking either the vertices both in L and in G i or the vertices both in R and in G i . As L is a maximum-weight stable set in G (containing all the vertices both in L and in G i , for each i), this implies that we have the following characterization: a stable set in G has maximum weight if and only if, for each i, it contains either all the vertices both in L and in G i or all the vertices both in R and in G i .

We construct another directed graph from G, denoted by -→ G : there is a vertex i for each G i , and an arc between two vertices i and j if and only if there exists an edge uv in G such that u is both in G i and in L, and v is both in G j and in R. Note that, by the denition of -→ G and the characterization of maximum-weight stable sets in G, if a maximum-weight stable set in G contains all the vertices both in G i and L for some i, then it must contain all the vertices both in G j and L, for all successors j of i in -→ G . We also dene the following relationship between two vertices u ∈ R and v ∈ L of G: u v if and only if u and v belong to G i for some i, or u ∈ G i and v ∈ G j , and there exists a directed path from i to j in -→ G . From the above discussion, for any pair of vertices u, v such that u v, any maximum-weight stable set in G contains either u or v. Hence, taking any d pairs of vertices u i , v i such that u i v i for each i yields a d-transversal for α(G) of size 2d. Note that, since L and R are two disjoint maximum-weight stable sets in G, any d-transversal for α(G) must contain at least 2d vertices.

The third step consists in constructing another bipartite graph associated with G, denoted by G: the vertices of G are the vertices of G, and there is an edge between two vertices u and v with cost c(u) + c(v) if and only if u v. We also add in G an isolated edge of cost c(v) for each forced vertex v that was in G. Then, it is not hard to see that there is an equivalence between d-transversals for α(G) obtained as described above (when, in addition, we allow forced vertices) and matchings of size d in G.

A rather technical proof allowed us to establish that the minimum size of a maximum-weight stable set in G is equal to ν( G), which implies that computing a minimum-cost d-transversal for α(G) containing only forced vertices and pairs of vertices u i , v i such that u i v i for each i is equivalent to nding a minimum-cost matching of size d in G. Another technical proof establishes that this is the only way of obtaining inclusion-wise minimal dtransversals for α(G) in bipartite graphs, concluding the whole proof.

We make two last remarks. On the one hand, we previously obtained similar results for trees in [BCdW + 11], before we managed to generalize them to bipartite graphs. On the other hand, the above characterization of maximum-weight stable sets in bipartite graphs enabled us to obtain in [BCP + 12] similar results when the graph parameter is not α(G), but the minimum weight of a vertex cover (a well-known related parameter).

Minimum blockers for the chromatic number

This section reviews results about a variant of the blocker notion as dened in Section 4.1: here, we want to decrease by at least 1 the chromatic number χ(G) of a graph G by removing as few edges as possible. A set of edges whose removal decreases the chromatic number of a graph G by at least 1 will be called a chromatic blocker for G. A related problem is the following: we want to decrease by at least 1 the stability number of a graph G by adding as few edges as possible. A set of non-edges whose addition decreases the stability number α(G) of a graph G by at least 1 will be called a stability blocker for G. As in the previous sections, and for similar reasons, proving that such a problem belongs to NP (or not) may be a hard task.

Note that, when looking for a minimum-size chromatic blocker for a graph G, we can assume without loss of generality that χ(G) ≥ 3, as the problem is trivial otherwise: a graph can be colored with only one color if and only if it has no edge. For similar reasons, when looking for a minimum-size stability blocker for G, we can assume without loss of generality that α(G) ≥ 3.

It is easy to see that nding a minimum-size chromatic blocker in a complete graph is trivial, as one edge is enough. Similarly, any minimum-size stability blocker in a graph with no edge consists of only one edge. However, we showed in [START_REF] Bazgan | Blockers for the stability number and the chromatic number[END_REF] that both problems are NP-hard in general: Theorem 4.8 [START_REF] Bazgan | Blockers for the stability number and the chromatic number[END_REF]). Determining the minimum size of a chromatic blocker (resp. of a stability blocker) is an NP-hard problem.

For the stability blocker, the proof uses a polynomial Turing reduction from the problem of computing α(G) for a graph G. Let G 1 , . . . , G n be n copies of G, where n is the number of vertices of G. For each i, add a set I i of i + 1 isolated vertices, and an edge between each of these vertices and any vertex of G i . We ask whether, in each G i ∪ I i , there exists a stability blocker containing only one edge. If i ≥ α(G), then such an edge can be used to decrease the stability number of I i (and hence of G i ∪ I i ) by 1, and hence the answer is yes. If i = α(G) -1, then we need to add one edge to decrease the stability number of I i and at least one edge to decrease the stability number of G i , and hence the answer is no, concluding the proof.

CHAPTER 4. BLOCKERS AND D-TRANSVERSALS IN GRAPHS 52

Because of these NP-hardness results, we then studied the problems in relevant special cases. We rst considered the case of split graphs, i.e., graphs whose vertex set can be partitioned into a stable set S and a clique K: Theorem 4.9 [START_REF] Bazgan | Blockers for the stability number and the chromatic number[END_REF]). A minimum-size chromatic blocker (resp. stability blocker) can be determined in polynomial time in split graphs.

For the chromatic blocker, we can assume without loss of generality that the chromatic number is the size of K. If K has at least 4 vertices, then removing two disjoint edges is enough: the chromatic number of K decreases by 2, and we use an additional color for S if needed. Otherwise, K is a triangle, and removing its 3 edges is enough to obtain a bipartite graph. In both cases, we obtain chromatic blockers of size at most 3, and a minimumsize chromatic blocker can thus be determined by brute-force enumeration.

For the stability blocker, we can assume without loss of generality that the stability number is the size of S. We choose 3 vertices in S, and add three edges between them to obtain a triangle. The stability number of S decreases by 2, and we can select at most one additional vertex from K in any stable set. This stability blocker has size 3, and thus a minimum-size stability blocker can be determined by brute-force enumeration.

The second special case that was considered in [START_REF] Bazgan | Blockers for the stability number and the chromatic number[END_REF] is the one of complements of bipartite graphs. Computing a minimum-size stability blocker is trivial in this case (as α(G) = 2 for such a G), so we are interested in chromatic blockers. We provided in [START_REF] Bazgan | Blockers for the stability number and the chromatic number[END_REF] a full characterization of the value taken by the minimum size of a chromatic blocker in such graphs, based on a rather long case analysis involving seven conditions. However, proving that the problem is polynomial-time solvable is much easier: Theorem 4.10 ([BBPR15]). A minimum-size chromatic blocker can be determined in polynomial time in the complements of bipartite graphs.

Properly coloring the vertices of a graph G always consists in covering them by stable sets. However, in this special case, the only possible stable sets are non-edges and isolated vertices. If G contains at least 2 disjoint stable sets of size 2 (note that there necessarily exists a proper optimal vertex coloring that uses them), then we can merge them into a single stable set of size 4 by removing at most 4 edges. Otherwise, either the graph has at most 3 vertices or there exist at least 2 stable sets of size 1, and we can merge two such stable sets into a stable set of size 2 by removing one edge. In both cases, we obtain chromatic blockers of size at most 4, and a minimum-size chromatic blocker can thus be determined by brute-force enumeration.

The last special case that was considered in [START_REF] Bazgan | Blockers for the stability number and the chromatic number[END_REF] is the one of bipartite graphs. Computing a minimum-size chromatic blocker is trivial in this case, so we are interested in stability blockers. We provided in [START_REF] Bazgan | Blockers for the stability number and the chromatic number[END_REF] the following characterization for determining the minimum size of a stability blocker in such graphs, based on the partition described in Section 4.3: CHAPTER 4. BLOCKERS AND D-TRANSVERSALS IN GRAPHS 53 Theorem 4.11 ([BBPR15]). Let G be a bipartite graph, and let G 1 , . . . , G h be the (unique) partition of the free vertices of G, i.e., G i is the ith connected component of the graph obtained by removing, from the subgraph of G induced by the free vertices, the edges associated with the forbidden arcs of the directed graph G . The minimum size of a stability blocker in G is equal to:

• 1 if and only if G contains at least two forced vertices,

• 2 if and only if G contains at most one forced vertex, and: • 3 if and only if we are not in the above cases and there exist two integers i and j such that i = j and G contains an edge having one endpoint in G i and one endpoint in G j ,

• 4 otherwise. In this chapter, we review results about several variants of Steiner tree problems. Let T be a set of K terminal vertices, or simply terminals, in a connected undirected graph G where each edge e has a cost (or length) c(e) ∈ Q + . A Steiner tree in G is a tree covering the K terminals: as G is assumed to be connected, such a tree always exists (take any spanning tree, for instance). Moreover, the vertices in G that do not belong to T are called Steiner vertices. We shall also consider the case of directed graphs: in this case, we are interested in rooted Steiner trees. Let r be a root vertex (or simply root) in a graph G: there must be a (directed) path from r to any vertex in G. A rooted Steiner tree in G with respect to r is a Steiner tree rooted at r in G; we shall omit with respect to r except when necessary.

In undirected graphs, a rooted Steiner tree can be viewed as a Steiner tree covering both T and r, which can be ensured by adding r to T . Hence, in this case, there is no need to consider rooted Steiner trees explicitly.

The minimum (rooted) Steiner tree problem (MinSteinerTree) is to determine a tree S in G, rooted at r, spanning all the terminals and having minimum total length (or cost). As any Steiner tree must cover pre-specied vertices (the terminals), this is clearly a covering problem. The case where G is undirected has been widely studied: it has many applications, as shown in [START_REF] Cheng | Steiner Trees in Industry[END_REF][START_REF] Hwang | The Steiner Tree Problem[END_REF], and the associated decision problem was one of R. Karp's 21 NP-complete problems [START_REF] Garey | Computers and Intractability: a Guide to the Theory of NP-completeness[END_REF]. Also note that Steiner trees are actually the basic routing components used for multicast routing in networks.

When all vertices are terminals, MinSteinerTree becomes the minimum spanning tree problem, which is well-known to be solvable in polynomial time, using for instance greedy algorithms, such as the ones of Kruskal or Prim. In general, however, MinSteinerTree is APX-hard, although it can be solved in FPT time with respect to the number of terminals [START_REF] Dreyfus | The Steiner problem in graphs[END_REF],

and admits constant-factor approximation algorithms [START_REF] Hwang | The Steiner Tree Problem[END_REF][START_REF] Robins | Improved Steiner tree approximation in graphs[END_REF].

56

Note that, in this problem, requiring that any feasible solution is a Steiner tree is actually not explicitly needed: it is sucient to require that we can route 1 unit of ow from r to each terminal (i.e., any feasible solution covers all the terminals), and that, if an edge is used by at least 1 unit of ow, then its full cost must be paid. In this way, any optimal solution has to be a tree; otherwise, it can easily be transformed (by rerouting ow units if needed) into a feasible solution that is a Steiner tree, without increasing the total cost. This may not be the case when additional constraints are considered.

There are less results about the case where the graph is directed, which is a generalization of the undirected case; only non constant ratio approximation algorithms are known [10]. Such a case occurs, for instance, when considering multicast routing in asymmetric networks [START_REF] Lefebvre | Optimization of information ows in telecommunication networks[END_REF]. Note that, unlike in undirected graphs, this case also generalizes the well-known set cover problem (SetCover), even in directed acyclic graphs. In SetCover, we are given a set of elements E, and a set X of subsets X 1 , . . . , X ν of elements of E, and we want to determine the minimum number of subsets from X needed to cover all the elements of E (an element e of E is covered by X i if e belongs to X i ). The decision version of the problem is to decide whether all the elements of E can be covered by a given number of subsets from X.

On the one hand, a logarithmic inapproximability bound is known for SetCover [START_REF] Feige | A threshold of ln n for approximating set cover[END_REF], and the best lower bound known for the approximability of MinSteinerTree in directed graphs is actually based on this result and on the fact that SetCover polynomially reduces to MinSteinerTree in directed acyclic graphs. On the other hand, the best upper bound known for the approximability of MinSteinerTree in directed graphs is polynomial in K: namely, there exists a O(K )-approximation algorithm for this problem, for any > 0 [10]. Moreover, no better approximation algorithm is known for the special case of MinSteinerTree in directed acyclic graphs either.

Steiner trees with a bound on the number of branching or diusing nodes

In this section, we consider two generalizations of MinSteinerTree, studied during the PhD thesis that D. Watel did under the supervision of D.

Barth, M.-A. Weisser and myself. Given a Steiner tree S rooted at a vertex r, a branching vertex is a vertex having at least two children in S. The rst generalization, which consists in nding a minimum-cost Steiner tree having at most a given number p of branching vertices, was introduced in [START_REF] Watel | Steiner problems with limited number of branching nodes[END_REF] and motivated by a routing problem in optical networks. Actually, installing a device that enables a vertex to duplicate the data it receives may be costly in such networks, and therefore, in practice, the number of vertices that can duplicate data is limited by the available budget. Hence, if we route the data along a Steiner tree, as it is commonly the case, we obtain the above problem.

Given a Steiner tree S rooted at vertex r, we dene the pattern of S as the tree obtained from S by iteratively contracting any edge having at least one endpoint which is both dierent from r and neither a terminal nor a branching vertex. In the pattern of S, the only vertices are then r, terminals, and branching vertices. By enumerating all the possible patterns of a (minimum-cost) solution, and then extending every pattern to a solution (whenever this is possible) by computing vertex-disjoint paths (of minimum total cost) between the endpoints of each edge of the pattern, we can show: Theorem 5.4 ([WWBB13]). When K = O(1), the problem of nding a minimum-cost Steiner tree with at most p branching vertices is:

• polynomial-time solvable in planar directed graphs if all costs are 0,

• polynomial-time solvable in undirected graphs if all costs are 0,

• polynomial-time solvable in undirected graphs of bounded tree-width.

Note that the complexity of the problem with arbitrary costs remains open in the rst and second cases of Theorem 5.4.

To dene the second generalization of the (rooted) Steiner tree problem that we shall consider, we need to introduce several notions. Given a graph G, the shortest paths graph of G (or metric completion of G) is the graph whose vertices are the ones of G, and in which there is an edge between any two vertices u and v, whose cost is the distance between u and v in G.

Given a Steiner tree S rooted at a vertex r in the shortest paths graph of a graph G, a diusing vertex in G is a branching vertex of S in the shortest paths graph of G. In this setting, any vertex is actually assumed to be able to transmit a data to several successors, provided that it receives the data enough times. If the same data is sent several times to a vertex, then, for instance, the cost of sending it twice is twice the cost of sending it once. On the contrary, a diusing vertex is able to transmit a data to several successors, even if it receives the data only once. Hence, any vertex can be a branching vertex, but a diusing vertex shall be a branching vertex (otherwise, making it a diusing vertex is useless). In the remainder of this section, we consider the problem of nding an optimal routing in a graph G having at most d diusing vertices, i.e., a minimum-cost Steiner tree in the shortest paths graph of G rooted at r and that has at most a given number d of branching vertices. Note that such a Steiner tree always exists (for instance, take any hamiltonian path starting at r in this complete graph).

In [START_REF] Watel | An FPT algorithm in polynomial space for the directed steiner tree problem with limited number of diusing nodes[END_REF], we showed the following positive result regarding the parameterized complexity of the problem with respect to K: Theorem 5.5 [START_REF] Watel | An FPT algorithm in polynomial space for the directed steiner tree problem with limited number of diusing nodes[END_REF]). A minimum-cost routing with at most d diffusing vertices can be computed by an algorithm that is FPT with respect to K, while using only polynomial space. In particular, when d = K -1, the algorithm returns a minimum-cost Steiner tree. This algorithm is obtained by combining the notion of pattern mentioned above (but where the non-leaf vertices of the pattern are not labeled, and hence the number of patterns that need to be considered in this case is FPT with respect to K) and a dynamic programming approach, which computes the best solution associated with each pattern. Note that it was known for a long time that MinSteinerTree is FPT with respect to K using dynamic programming only [START_REF] Dreyfus | The Steiner problem in graphs[END_REF], but the only known algorithms that use polynomial space are not FPT. For instance, the algorithm in [START_REF] Fomin | Computing optimal steiner trees in polynomial space[END_REF] runs in time O(5.96 K n O(log(K)) ) in graphs with n vertices, while the algorithm in [START_REF] Nederlof | Fast polynomial-space algorithms using inclusion-exclusion[END_REF] is FPT with respect to K only when all costs are O(1) (when costs are arbitrary, a pseudo-polynomial factor appears in its running time).

In [START_REF] Watel | Directed steiner tree with branching constraint[END_REF][START_REF] Watel | Directed steiner trees with diusion costs[END_REF], we obtained the following results regarding the parameterized complexity of the problem with respect to d: If G is undirected and e = (u, v) is an arc of S, then [u, v] must be an edge of G. Note that MinSteinerTree is the special case of MinCap-SteinerTree where capa(e) = K for all e ∈ E (in this case, a feasible solution always exists). MinCapSteinerTree appears naturally in several contexts, for example in the design of wind farm collection networks [START_REF] Hertz | Optimizing the Design of a Wind Farm Collection Network[END_REF] or of telecommunication networks [START_REF] Cheng | Steiner Trees in Industry[END_REF], or in power distribution system optimization [START_REF] Duan | Distribution System Optimization by an Algorithm for Capacitated Steiner Tree Problems with Complex ows and Arbitrary Cost Functions[END_REF]. When c(e) = 0 for all e ∈ E, MinCapSteinerTree turns into a decision problem: determine whether there exists or not a tree rooted at r, spanning all the terminals, and not violating the capacity constraints.

When K = n -1, i.e., any feasible solution is a spanning tree, MinCap-SteinerTree is solvable in polynomial time if capa(e) = 2 for all e ∈ E, while it is NP-hard if capa(e) = 3 for all e ∈ E [START_REF] Garey | Computers and Intractability: a Guide to the Theory of NP-completeness[END_REF]. In [START_REF] Arkin | The (K, k)-Capacitated Spanning Tree Problem[END_REF][START_REF] Jothi | Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design[END_REF], the authors provide approximation algorithms for a variant of MinCapSteinerTree where the capacities are uniform and there always exists a feasible solution, since it is assumed that the input graph is a metric completion.

Our main result in [START_REF] Bentz | On the edge capacitated steiner tree problem[END_REF] is a complete characterization of the complexity of MinCapSteinerTree, which enables us to distinguish between easy and hard cases of the problem for digraphs, directed acyclic graphs and undirected graphs. In particular, we show that there are strong links between MinCapSteinerTree and another well-known graph optimization problem, namely nding vertex-disjoint paths of minimum total length between source-sink pairs. Moreover, whenever MinCapSteinerTree with arbitrary lengths is intractable while the case with lengths 0 is not, we provide approximation results for MinCapSteinerTree nearly as good as the best ones for MinSteinerTree. Therefore, any inapproximability result we obtain is in fact an intractability result for the case with lengths 0.

CHAPTER 5. STEINER TREES & RELATED VARIANTS 61

Note that any undirected instance of MinCapSteinerTree can be transformed into a directed one by replacing each edge by two opposite arcs with the same length and capacity. Hence, any positive result (existence of a polynomial-time algorithm or approximation result) for directed graphs also holds for undirected graphs, while any negative result for undirected graphs (NP-hardness or inapproximability result) also holds for directed graphs.

Apart from the assumption on the graph itself (undirected, directed with or without circuits), several parameters are considered. Namely, the number K of terminals, the minimum and maximum edge capacities, and the edge lengths: K can be O [START_REF] Adamy | Call Control in Rings[END_REF] or not; the minimum and maximum edge capacities can be non depending on K, they can be greater than or equal to K -κ (1 ≤ κ ≤ K -1), and they can be equal (uniform capacity) or not; the edge lengths can be all equal to 0, all equal to a positive value (i.e., uniform), or non uniform. In [START_REF] Bentz | On the edge capacitated steiner tree problem[END_REF], we settle all cases except one, namely the undirected case with uniform capacity and xed K ≥ 3, but we prove that MinCapSteinerTree is then equivalent to nding, in an undirected graph, vertex-disjoint paths of minimum total length linking O(1) source-sink pairs, a problem whose complexity is a long-standing open question [START_REF] Kobayashi | On Shortest Disjoint Paths in Planar Graphs[END_REF].

The three trees drawn in Figure 5.1 provide a picture of the possible cases for the three types of graphs (undirected or directed graphs, acyclic or not). The numbers assigned to the leaves of these trees refer to the theorems that were used to prove the associated results, but we will not detail them further here: two leaves where the same number appears simply correspond to results that are proved by the same theorem. The values of the three parameters appear on the branches and each branching node corresponds to a partition of the possible cases: the value on a branch excludes the values on the branches to the left. For instance, in undirected graphs, the capacities can be either all equal to 1, or at least K -1, or uniform of value at least 2 and at most K -2, or, nally, any other values not yet considered. Moreover, if a leaf corresponds to a branch where the values of some of the parameters are unspecied, then this means that the associated result holds even in the most general case (if it is a positive, i.e., tractability result) or in the most specic case (if it is a negative, i.e., hardness result) with regard to the unspecied values. For instance, the NP-hardness result associated with Leaf 7 holds even if K is xed (i.e., if K = O(1)) and if all lengths are 0 (since neither the value of K nor the lengths appear on this branch), and the result associated with Leaf 11 holds for any lengths and any capacities (since only the assumption on K being xed appears on this branch).

Therefore, for digraphs, the branch any capacity includes the case of uniform capacities between 2 and K -2 for K xed (or not). Also note that, if the capacity is uniform and K = O(1), then there exists some constant κ such that all capacities are equal to K -κ: hence, in the tree associated with undirected graphs in Figure 5.1, the branch any capacity, which leads to Leaf 8, excludes the case where K is xed (contained in Leaves 9 and 10). The rst set of results has been obtained during the PhD thesis that T. Lefebvre did under the supervision of S. Elloumi, E. Gourdin (research engineer at Orange Labs) and myself. The purpose of his thesis was to provide answers to the following question: given a telecommunication network that supports multicast routing, is there some benet (in terms of cost, or in terms of achievable throughput) to also use network coding ?

In order to support multicast routing (see also Sections 5.1 and 5.2), a network must allow any of its nodes to copy the data it receives, and then emit it towards all its successors (even if the data was received only once).

While a classical routing (or ow) can be viewed as an assignment of values to a set of paths, linking a given source to a given sink (see Section 2.1), a multicast routing (or Steiner ow ) can be viewed as an assignment of values to a set of Steiner trees, linking a given source to a given set of terminals. This also means that a multicast routing can be viewed as a fractional packing of Steiner trees (i.e., of structures covering both the source and the terminals).

Roughly speaking, using network coding can be viewed as combining (with the help of a so-called coding scheme ) several data received by a node into a single data, which will be emitted towards its successors. It can be proved that, if the network is represented by a directed graph, then a routing using both multicast and network coding can be viewed as the superposition of several maximum ows (i.e., any one of them can use all the capacity available on each arc), namely one from the source to each terminal.

In both cases, we want to dene a static routing, i.e., one that cannot be modied even if some edge failure occurs in the network. For such a routing, its residual throughput is the throughput that is still achieved by this routing, even if any edge can fail (this corresponds to the worst case).

The initial question was actually studied in several settings [START_REF] Lefebvre | Optimization of information ows in telecommunication networks[END_REF]:

• when each edge has a convex cost function, and the goal is to minimize the total cost while ensuring a given throughput,

• when there are actually several sources, each with its own set of terminals (multi-commodity case) and an associated weight, and the goal is either to maximize the total weighted throughput, or to maximize the common throughput of all commodities (fairness requirement),

• when there can be one edge failure in the network, and the goal is either to minimize the total cost for a given residual throughput (each edge having an integral cost) or to maximize the residual throughput.

CHAPTER 5. STEINER TREES & RELATED VARIANTS 64

Moreover, in each setting, the network (graph) can be either undirected, bi-directed, or directed. Each setting has an associated gain, dened as the ratio between the optimal throughput of a multicast routing using network coding and the optimal throughput of one not using it (reverse the ratio if costs are considered). Obviously, such a ratio is at least 1, and, in each setting, theoretical upper bounds on it are provided [START_REF] Lefebvre | Optimization of information ows in telecommunication networks[END_REF][START_REF] Bentz | Network coding for survivable multicast video streaming networks[END_REF][START_REF] Bentz | On the minimum convex cost multicast ow problem[END_REF].

This gain is also computed on real-life instances, which requires in particular to compute the optimal value of the multicast routing without network coding (for the multicast routing with network coding, this is generally much easier, as it amounts to solving a linear program or a convex problem). In the case of convex cost functions, this is essentially done by using Frank-Wolfe The problem studied during the Master's internship of T. Ridremont can be viewed as a reliable Steiner tree problem, and consists in computing an optimal Steiner tree rooted at some given vertex r, when all vertices, except r, are terminals (so any Steiner tree is in fact a spanning tree), and we want to minimize, in the worst case, the number of terminals (i.e., vertices)

disconnected from r when we delete some edge from the graph. This is a reliable Steiner tree problem in the sense that we want to minimize the biggest impact that one edge failure can cause in the network.

We proved the following hardness result:

Theorem 5.10 ( [START_REF] Ridremont | Optimisation robuste du câblage dans les parcs d'énergie renouvelable (in French)[END_REF]). Determining a spanning tree, rooted at a given root vertex r, and minimizing the maximum number of vertices disconnected from r when any one edge is removed, is strongly NP-hard.

This is proved via a reduction from the problem 3-Partition, a variant of the problem Partition dened in Section 3.4, which is strongly NP-hard.

Several ILP formulations for this problem and some of its variants were also proposed and tested on real-life instances.

The basic problem studied during the PhD thesis of T. Ridremont can be viewed as a reliable Steiner network problem. A (rooted) Steiner network in a graph G is a connected subgraph of G that covers all the terminals (and the root), but is not required to be a tree. In particular, if we add edge capacities (as in Section 5.3) or if we want the network to be resilient to one edge failure, or both, then optimal solutions will not (always) be trees.

CHAPTER 5. STEINER TREES & RELATED VARIANTS 65

Given a graph with a root vertex r, edge costs, and edge capacities, the problem that we consider thus consists in determining a minimum-cost

Steiner network rooted at r such that, for any edge e, there exists a ow in this network that does not use e and simultaneously conveys 1 unit of ow from r to any terminal, while respecting the edge capacities.

This problem is NP-hard, and quite hard to solve eciently in practice.

In order to solve it exactly, three formulations were developed in [START_REF] Bentz | Formulations for designing robust networks. an application to wind power collection[END_REF].

The rst one is an ILP based on ow variables with two indices, and has a polynomial (but big) number of variables and constraints. However, the optimal value of its continuous relaxation is not good enough, and hence it cannot be used in practice to solve the problem when the input graph has more than forty or fty vertices, even with a commercial solver like CPLEX.

The second one is an ILP based on a cutset formulation, and has few variables but an exponential number of constraints. It can be solved by column generation, and provides better results than the previous formulation.

The third and last one is a bi-level program, whose second level is a min max problem, the max part being actually a maximum ow formulation.

Since this linear programming formulation is well-known to have a totally unimodular constraint matrix, one can forget the integrality constraints, replace this linear program by its dual one, and obtain a minmin problem, which is easily seen to be equivalent to a simple min problem. Then, this new bi-level program can be solved by considering the convex hull corresponding to the feasible integral solutions of the problem at the second level, and progressively generating (by using a constraint generation procedure) the constraints associated with the extreme points of this convex hull. The subproblem used to generate these constraints is hard but far smaller than the original one, and in the end this formulation reveals to be the most ecient one. Moreover, it is almost oblivious to the number of edges that can fail, and hence, unlike the two previous ones, it can be used to solve the problem eciently even when several edges can fail (instead of one only).

Chapter 6

Conclusions and perspectives

Throughout this report, several partial conclusions on some general questions about families of packing and covering problems in graphs have been reached and highlighted. Some are specic to one or two of these families, others are common to all of them. For instance, given some basic problem in one of the families of covering problems, one of these major general questions is: what kind of packing constraints are we allowed to add to the basic problem in order to ensure that we stay suciently close to it ? Here, staying close would simply mean keeping most of its good properties. Another related one would be to add packing constraints to the basic problem in order to be suciently far from it.

Concerning integral multiows and multicuts, the number of elements (i.e., paths) to be packed or covered can be exponential in the size of the input graph. Even restricting the number of source-sink pairs is not sucient to change this fact, although this sometimes does make MinMC easier, and sometimes not (see Section 2.3). Similarly, adding constraints such as the ones considered in Section 2.4 (cardinality constraints, or requiring only a partial covering) does not always make the problem harder, or easier. The results from these two sections are thus a rst step towards understanding which types of constraints lead to harder problems, and which do not.

Another relevant question is: can we nd necessary and/or sucient conditions for the ratio between the optimal values of MinMC and MaxIMF to be O(1), or at least small enough ? This question has been studied in Section 2.2, but, again, only partial answers are known. Quite recently, two very nice papers involving Julia Chuzhoy and David Kim led, on the one hand, to a slightly improved upper bound for this ratio in planar graphs, and, on the other hand, to an improved inapproximability bound for MaxIMF, also in planar graphs (the best lower bound previously known was APXhardness) [START_REF] Chuzhoy | Improved approximation for nodedisjoint paths in planar graphs[END_REF][START_REF] Chuzhoy | New hardness results for routing on disjoint paths[END_REF]. However, the gap between these two bounds remains signicant, meaning that there is still a lot of room for improvement. More details on nine other problems in this eld of research, which were mentioned as open and particularly worth studying in [START_REF] Bentz | Résolution exacte et approchée de problèmes de multiot entier et de multicoupe : algorithmes et complexité[END_REF], and which have not all been settled, can be found in Appendix A.

Concerning coloring problems, and their links to discrete tomography, the complexity of the generalization of the basic problem described by Ryser that uses three colors instead of two remained open for a long time, before Dürr et al. were nally able to settle it [START_REF] Dürr | Reconstructing 3-Colored Grids from Horizontal and Vertical Projections is NP-Hard: A Solution to the 2-Atom Problem in Discrete Tomography[END_REF] (see Section 3.1). However, this case represents a kind of boundary case: with two colors, the problem is easy; with three or more colors, it becomes hard. So, the general question we really want to fully answer is: when there are three colors, can we characterize the kind of structures that we can impose on the solutions we want to obtain, in order to make the problem easy ? Sections 3.2 and 3.3 provide partial answers (even for proper colorings), but we are still far from a characterization. Concerning d-transversal and blocker problems, the number of elements (i.e., optimal solutions to a graph optimization problem) to be covered can also be exponential in the size of the input graph. This is one of the reasons why proving that such a problem belongs to NP or not may be a hard task, depending on the graph parameter that is considered. Actually, the fact that the nature of a d-transversal problem is heavily inuenced by the graph parameter it is related to also implies that there is not really a basic problem in this case. Therefore, it is hard to identify general properties or ideas common to all d-transversal problems (apart from the hardness of relating them to NP). In Sections 4.2 to 4.4, structural results are provided for several special cases, illustrating for instance the fact that switching from regular bipartite graphs to nearly regular bipartite graphs (such as the rectilinear grids) can strongly impact the structure of optimal solutions. A natural way of looking for general ideas, which may be good candidates for being common to all d-transversal problems, would be to consider solving these problems with approximation (instead of exact) algorithms. This may still be hard, especially when problems are not known to be in NP, but this is worth trying as this seems like a promising lead that, to the best of our knowledge, was not studied yet (although some papers did study the approximability of related, but easier, problems [START_REF] Zenklusen | Matching interdiction[END_REF]).

Finally, concerning problems related to Steiner trees and networks, the ones that have been studied in Chapter 5 either stay close to the classical Steiner tree problem (for instance, when limiting the number of diusing nodes) or not (for instance, when limiting the number of branching nodes, or when adding capacities, except in very special cases). Indeed, in some of these variants, it becomes necessary to require that the feasible solutions are trees (otherwise, even optimal solutions may not be trees), and sometimes there does not even exist feasible solutions. CHAPTER 6. CONCLUSIONS AND PERSPECTIVES 69 Again, the initial question was: can one exhibit natural sucient (either necessary or not) conditions on the packing constraints to be added in order to ensure that the problem obtained stays close enough to the classical Steiner tree problem ? The results presented in Sections 5.2 and 5.3 provide some partial answers, and should be completed in this perspective.

Another aspect that has been studied (see Section 5.4) was the impact of a failure on a static multicast routing, i.e., on a set of Steiner trees, or on a Steiner network. But what about the case where, whenever one edge fails, one wants to ensure, at minimum cost, that there still exists a routing using a single Steiner tree, while not violating any capacity constraint? This is dierent both from using a Steiner network (in which the data that must reach each terminal can be routed along several paths) and from considering a static routing on a set of Steiner trees, and this setting also generalizes the one considered (and fully characterized) in Section 5.3, which would correspond to the case where no edge can fail.

Moreover, this can make things considerably easier in some situations.

For instance, if the graph represents a network used for collecting or distributing electrical power, taking into account the physics equations corresponding to the way the energy is routed inside the network amounts to adding non linear constraints (known as load-ow equations, or power-ow equations) to the model. However, if the energy is assumed to be routed along a Steiner tree, then it can be shown that these non linear equations simply turn into classical ow conservation and capacity constraints, which are linear constraints. This is also a particularly relevant and challenging way of combining covering problems with reliability issues, as well as relating covering problems with additional capacity (i.e., packing) constraints to the design of power distribution (or power collection) networks.

a

  ij x j ≤ b i ∀i ∈ {1, . . . , m}(1.1)

  MaxIMF and MinMC, described above. If, given an edge-capacitated graph G (along with a list of source-sink pairs), one knows both a feasible solution F to the instance of MaxIMF dened on G and a feasible solution C to the instance of MinMC dened on G that are such that val(C) ≤ α • val(F ), where val(C) and val(F ) denote the respective values of C and F , then

F

  and C are α-approximate solutions for the instances of MaxIMF and MinMC (respectively) dened on G. For instance,Garg et al. designed

  , which means O( |V |) in sparse graphs where |E| = O(|V |) (e.g., planar graphs). However, it was highlighted in [Ben09a] that SP F can behave very badly even on some simple families of trees, by providing such families where the ratio of O( |V |) is actually reached. Hence, even for what seems like simple instances, relying on a heuristic CHAPTER 2. INTEGRAL MULTIFLOWS & MULTICUTS 12 based solely on this principle may result in providing very bad solutions, although such a heuristic does work well in practice whenever suciently short paths are available for routing.

Figure 2 . 1 :

 21 Figure 2.1: Edge-disjoint paths in a rectilinear grid.

  in polynomial time, by preprocessing the digraph and then applying Garg et al.'s algorithm. I also described in [Ben07] a family of instances showing that the ratios 2 log 2 (|T |) and 2 log 2 (|T L | + 2) are essentially tight. However, this does not necessarily mean that there exists no way of determining a feasible integral multiow F and a feasible multicut C satisfying val(C) = O(val(F )), and so this very question is still an open one. Here is the second set of results: Theorem 2.6 ([Ben07]). If we consider the restriction of MaxIMF and MinMC to multiterminal instances dened on directed graphs, we have: • If |T L | = 0, or if |T L | = 1 and |T | = 2, then any optimal integral multiow F and any optimal multicut C satisfy val(F ) = val(C), and such optimal solutions can be computed in polynomial time,

Theorem 2 .

 2 10 ([Ben08]). MinMC is APX-hard in digraphs with bounded directed tree-width.One of the ten main open questions that I mentioned in my PhD thesiswas: what is the complexity of MinMC in directed acyclic graphs with O(1) source-sink pairs? I kept on working on this question, and was nally able to deal with both of the above questions at the same time in[START_REF] Bentz | On the hardness of nding near-optimal multicuts in directed acyclic graphs[END_REF]:

Figure 2 . 2 :

 22 Figure 2.2: A counter-example to the proof of Yeh's algorithm.

Theorem 2 .

 2 21[START_REF] Bodic | Variantes non standard de problèmes d'optimisation combinatoire[END_REF][START_REF] Bentz | On the complexity of partial colored multiterminal cut problems[END_REF]). Partial MinMC is polynomial-time solvable when min(tw(G + H), tw(G + H)) = O(1), tw(•) being the related tree-width.

Figure 3 . 1 :

 31 Figure 3.1: A forbidden conguration for Theorem 3.6. The black vertices are in L, the white ones are in R, and the number on each edge is its color.

Theorem 3 .

 3 15 ([BP09]). When both p and the number of colors k are O(1), we can solve Col-LocalBounds in polynomial time in trees.

+ 1 m

 1 09], we rst established, with the help of a rather intricate reduction from the NP-hard maximum clique problem, the complexity of nding a minimum-size blocker for ν(G) in arbitrary bipartite graphs: Theorem 4.1 ([ZRP + 09]). Determining the minimum size of a blocker for ν(G) is NP-hard in bipartite graphs. From this theorem and Proposition 4.1, nding the minimum size of a 1-transversal for ν(G) is also NP-hard in bipartite graphs. Actually, this can also be extended to d-transversals for d > 1: Theorem 4.2 ([ZRP + 09]). For any d ≥ 1, determining the minimum size of a d-transversal for ν(G) is NP-hard in bipartite graphs. This latter result is obtained by reducing the case d = 1 to the case where d can take any value, by adding to any initial bipartite instance a matching of size d -1. Moreover, note that, for any d ≥ 1, the decision version of the problem consisting in determining the minimum size of a d-transversal for ν(G) is actually in NP. More precisely, given any potential d-transversal T d in a graph G with m edges, checking that T d is indeed a d-transversal for ν(G) can be done by giving a weight 1 to any edge in T d and a weight 1 + to any other edge, and then computing a maximum matching of maximum weight, which can be done in polynomial time. If this maximum weight is at most ν(G)(1 + 1 m ) -d m , then any maximum matching must use at least d edges from T d , establishing that T d is a d-transversal for ν(G).

CHAPTER 4 .

 4 BLOCKERS AND D-TRANSVERSALS IN GRAPHS 45 Since the problem of determining the minimum size of a d-transversal for ν(G) is NP-hard in arbitrary bipartite graphs, we studied its complexity in several families of bipartite graphs in [ZRP + 09] and [RBP + 10]. For instance, the cases of chains and rings can be solved easily (the details, which are left to the reader, are also given in [ZRP + 09]). Another natural family of bipartite graphs is the class of regular bipartite graphs, for which we have: Theorem 4.3 ([ZRP + 09]). Given any bipartite graph G such that all n vertices have the same degree ∆, a minimum-size d-transversal for ν(G) can be found in polynomial time, by taking the d∆ edges incident to the vertices of any independent set of size d, for any d ∈ {1, . . . , n 2 }.

Figure 4 .

 4 1 illustrates the case where ∆ = 3 and d = 4: the solution obtained by taking the bold edges is a d-transversal of size d∆ = 12, and hence of minimum size, but it is also a matching.

Figure 4 . 1 :

 41 Figure 4.1: A matching of size 12 (in bold edges), which is also a minimumsize 4-transversal in a regular bipartite graph of degree 3.

CHAPTER 4 .

 4 BLOCKERS AND D-TRANSVERSALS IN GRAPHS 46 Lemma 4.1 ([RBP + 10]). Let G m,n be a rectilinear grid with m rows and n columns, m and n being even. A minimum-size d-transversal for ν(G m,n ) 1. (when m = 2 or n = 2)

Lemma 4 . 2 (

 42 [RBP + 10]). Let G m,n be a rectilinear grid with m rows and n columns, m and n being odd. A minimum-size d-transversal for ν(G m,n )1. (when m = 1 or n = 1)

Lemma 4 . 3 (

 43 [RBP + 10]). Let G m,n be a rectilinear grid with m rows and n columns, m being even and n odd. A minimum-size d-transversal for ν(G m,n ) 1. (when n = 1) • has size d for d ∈ {1, . . . , m 2 = ν(G m,1 )}.

2 . 47 •

 247 (when m = 2 and n ≥ 3) CHAPTER 4. BLOCKERS AND D-TRANSVERSALS IN GRAPHS has size 2d for d = 1 or d = 2.

Figure 4 . 2 :

 42 Figure 4.2: A dancat (in bold edges) on a grid.

Theorem 4 . 5 (

 45 [RBP + 10]). For any d ∈ {1, . . . , ν(G)}, the minimum size of a d-transversal for ν(G) can be computed in polynomial time in trees.

  (a) either G contains exactly one forced vertex, (b) or there is an i such that G i contains at least four vertices, (c) or G contains the graph in Figure 4.3 as a subgraph, (d) or G contains the graph in Figure 4.4 as a subgraph.

Figure 4 . 3 :

 43 Figure 4.3: A graph containing three vertices from L (black vertices) and three vertices from R (white vertices). The three rectangles represent three dierent graphs G i of the partition of G (each rectangle is such a graph).

Figure 4 . 4 :

 44 Figure 4.4: A graph containing four vertices from L (black vertices) and four vertices from R (white vertices). The four rectangles represent four dierent graphs G i of the partition of G (each rectangle is such a graph).

Theorem 5 .

 5 6 ([WWBB14, WWBB16]). When d = O(1), the problem of nding the minimum cost of a Steiner tree with at most d branching vertices in a shortest paths graph is polynomial-time solvable. Moreover, the problem is W[2]-hard with respect to d.The rst part of the theorem is proved by enumerating all the possible sets of at most d diusing vertices, and then nding a minimum-weight spanning tree. As in Theorem 5.3, the second part is proved by an FPT-reduction from the SetCover problem parameterized by the number of sets that can be in the solution, and shows that the rst part is essentially best possible, as the problem is unlikely to be FPT with respect to d. We also studied in [WWBB14, WWBB16] another parametrization of the problem: Theorem 5.7 ([WWBB14, WWBB16]). When K-d = O(1), the problem of nding the minimum cost of a Steiner tree with at most d branching vertices in a shortest paths graph is NP-hard. Finally, an approximation-preserving reduction from MinSteinerTree to the case where there are at most d diusing nodes implied two results, given in [WWBB14, WWBB16]. The rst one deals with MinSteinerTree: Theorem 5.8 ([WWBB14, WWBB16]). There is an K-1 d -approximation algorithm for MinSteinerTree that runs in polynomial time if d = O(1).

Figure 5 . 1 : 63 5. 4

 51634 Figure 5.1: An overview of the results giving a complete characterization of the complexity of nding Steiner trees satisfying given edge capacities.(Note that DAG stands for directed acyclic graph.)

  algorithm and dierential calculus, and solving a combinatorial Steiner tree problem at each step. In all other cases, this is done by using column generation, and solving a combinatorial Steiner tree problem (or some variant of it) to generate columns at each step. The second set of results was obtained during the Master's internship, and then the PhD thesis, that T. Ridremont did under the supervision of M.-C. Costa, one other researcher (D. Porumbel during the Master's internship and A. Hertz during the PhD thesis), and myself.

  The last two open problems related to Steiner trees that should once again be mentioned are actually long-standing open questions. First, can we design better approximation algorithms for the minimum rooted Steiner tree problem in directed graphs? Indeed, lower and upper bounds are known for the approximability of this problem, but the gap between them remains signicant. Second, can we solve in polynomial time the only case left as open in Section 5.3, or is it NP-hard? In other words, what is the complexity of the problem where one wants to determine vertex-disjoint paths of minimum total length linking O(1) source-sink pairs in an undirected graph? And what happens when the graph is a planar directed graph?

10

  Here is the second ILP. It models the minimum multicut problem (MinMC):

	min	capa(e)z e
	e∈E
	(ILP-MC ) s. t.	z e ≥ 1	∀j ∈ {1, . . . , |P|}	(2.2)
	e∈pj

  The second one is a negative one for the case with at most d diusing vertices, and is based on a complexity assumption dierent from P =NP: Assume each edge e has a capacity capa(e), i.e., an upper bound on the number of paths containing e and linking r to terminals. In other words, for every arc e = (u, v) in a Steiner tree S rooted at r, the subtree of S rooted at v must contain at most capa(e) terminals (with capa(e) ≤ K, without loss of generality), which adds a packing constraint to with |V | = n vertices; a set T = {t 1 , ..., t K } ⊂ V of K ≥ 2 terminals; a root vertex r ∈ V \ T ; two functions on E: a nonnegative length function c and a positive capacity function capa. Goal. Determine, if it exists, a minimum-length directed tree S rooted at r in G, spanning all the vertices of T and not violating the capacity constraints.

	CHAPTER 5. STEINER TREES & RELATED VARIANTS	60
	5.3 Steiner trees with edge capacities
	In this section, we consider another generalization of the (rooted) Steiner
	tree problem. MinSteinerTree, a covering problem. The minimum-length capacitated
	(rooted) Steiner tree problem (MinCapSteinerTree) is dened as follows:
	Minimum-length (rooted) Capacitated Steiner Tree Problem
	Theorem 5.9 ([WWBB14, WWBB16]). There is no O K d -approximation
	algorithm for computing the minimum cost of a Steiner tree with at most d branching vertices in a shortest paths graph unless NP⊆ZTIME[n log O(1) n ].

Input. A connected graph G = (V, E)

Note that, if the number of branching vertices must be at most p = K -1, then the problem is exactly MinSteinerTree. However, when p ≤ K -2, the problem is hard even with costs 0: Theorem 5.1 [START_REF] Watel | Steiner problems with limited number of branching nodes[END_REF]). For any p ≤ K -2, deciding whether there exists a Steiner tree with at most p branching vertices is NP-complete:

• in directed graphs, for any xed K ≥ 2.

• in planar graphs (directed or undirected).

To prove the rst part of this theorem, take any directed graph G and two source-sink pairs (s 1 , s 1 ) and (s 2 , s 2 ). Add a root r and K = 2 terminals t 1 and t 2 , as well as four arcs (r, s 1 ), (s 1 , t 1 ), (t 1 , s 2 ), (s 2 , t 2 ): then, nding a tree rooted at r that covers t 1 and t 2 with p = 0 amounts to nding in G two vertex-disjoint paths linking s 1 to s 1 and s 2 to s 2 respectively, which is an NP-complete problem [START_REF] Fortune | The directed subgraph homeomorphism problem[END_REF]. This reduction can be generalized to any value of p by adding a gadget linked to s 2 , in order to ensure that there can be no branching vertex inside G. The second part is proved by reduction from the NP-complete hamiltonian path problem, which consists in deciding whether there exists a path that goes through each vertex once and only once. By adapting the above reductions, we can also show: Theorem 5.2 [START_REF] Watel | Steiner problems with limited number of branching nodes[END_REF]). For any p ≤ K -2, the problem of nding the minimum cost of a Steiner tree with at most p branching vertices is NPhard to approximate within a ratio O(n 1-) for any > 0, even if a feasible solution always exists and is given in the input, in the following cases:

• in directed graphs with n vertices and unit costs, for any xed K ≥ 2.

• in planar graphs (directed or undirected) with n vertices and unit costs.

Note that this lower bound is best possible when all costs are 1, as taking any feasible solution yields a O(n)-approximation algorithm in this case.

In directed acyclic graphs, we have the two following results: Theorem 5.3 [START_REF] Watel | Steiner problems with limited number of branching nodes[END_REF]). When p = O(1), the problem of nding the minimum cost of a Steiner tree with at most p branching vertices can be solved in polynomial time in directed acyclic graphs. Moreover, the problem is W[2]-hard with respect to p in directed acyclic graphs.

The rst part of the theorem is proved by enumerating all the possible sets of at most p branching vertices, and then solving for each such set an instance of the minimum-cost ow problem. The second part is proved by an FPT-reduction from the SetCover problem parameterized by the number of sets that can be in the solution, and shows that the rst part is essentially best possible, as the problem is unlikely to be FPT with respect to p.

Appendix A: Open problems related to integral multiow and multicut problems

In my PhD thesis [START_REF] Bentz | Résolution exacte et approchée de problèmes de multiot entier et de multicoupe : algorithmes et complexité[END_REF], defended in 2006 and written in French, I provided a list of ten open problems related to integral multiows and multicuts, which I considered as major ones in this research eld. For the sake of completeness, I shall include them again in this report, in the same order as in [START_REF] Bentz | Résolution exacte et approchée de problèmes de multiot entier et de multicoupe : algorithmes et complexité[END_REF]:

1. What is the complexity of MaxEDP in (undirected or directed) planar graphs, when the number of source-sink pairs is O(1)?

2. What is the complexity of MaxEDP in graphs of bounded tree-width, when the number of source-sink pairs is O(1)?

3. What is the complexity of MaxEDP in graphs of bounded tree-width, when the maximum degree is O(1)? In this HDR thesis, we consider several families of packing and covering problems in graphs, namely:

• Multicuts and integral multiows, as well as some variants.

• Vertex and edge colorings with cardinality constraints, most of them being linked to a basic problem in discrete tomography.

• Blockers and d-transversals for some classical graphs parameters: the matching number, the stability number, and the chromatic number.

• Steiner trees and networks, as well as variants or generalizations (which are obtained, for instance, by adding edge or arc capacities, or by assuming that some edges or arcs can fail).

We study the computational complexity of all these problems, design approximation algorithms for some hard cases (or prove that such algorithms cannot exist), and exhibit several relevant parameters that allow to prove the xed-parameter tractability, with respect to such parameters, of some special cases (while other special cases are proved to be xed-parameter intractable).