Diminution Optimale de PAramètres d'un GraphE – DOPAGE

Nowadays, a major industrial issue is the concept of reliability. This notion is particularly crucial in fields involving network design or management. As soon as you provide services to customers for money, you have to make sure that you will be able to fulfil your part of the contract. Therefore, you must anticipate any event that might lead you to a situation where you are unable to do so. That is, you have to be reliable. For instance, if you must perform tasks involving some sort of network, then you are led to expect that this network does work. Designing or managing networks that do work thus appears to be essential. What sort of events could make a network break down' If the network is a telecommunication network (where each node is joined by links to other nodes, and nodes communicate with each other), some links or nodes may fail, and prevent other nodes from communicating at all. In such cases, you have to ensure that the network will still work at a certain level, which means that the failure of a single node or link must not bring the whole network to collapse. In other words, you must take this into account when designing the network (and when defining the routing policy). Graphs are formal objects particularly relevant for modeling various kinds of real-life objects, such as networks (nodes and links becoming vertices and edges, respectively). Many problems occurring in network design can then be translated in terms of graphs, and studied with the help of powerful tools from (algorithmic) graph theory. For instance, building reliable networks can be thought of as building graphs having specific properties. A basic example is the following: a graph is said to be k-connected if the minimum number of vertices (or edges) that one has to remove in order to disconnect the graph is at least k. Moreover, in this example, we define a graph to be reliable if, after one or several failures (on vertices or edges), the remaining vertices can still communicate with each other. Therefore, if you assume that at most k-1 vertices (or edges) can break down at the same time, then a network (graph) is reliable if and only if it is k-connected. This example is a classical one, however it may happen that the right notion of reliability associated with a particular network application is a different one. As an example, assume we are given a network in which nodes (computers) have to work in pairs for a specific reason: two computers can work together only if they are joined by a link (edge), and no computer works with more than one computer. We would like to get as many pairs of computers as possible. In terms of graphs, this problem is simply a classical maximum matching problem. However, as previously, it may happen that some vertices (or edges) break down. In this case, we are interested in determining the impact of such an event on the performance of the network. If, for instance, at most f failures happen on nodes (or edges) at the same time, what is the worst value of a maximum matching in the new network' Or, to put it in terms of reliability, can we ensure that, if f failures happen simultaneously, at least a sufficient number p of pairs of computers will continue to work together' In other words, is this network reliable' Although finding a maximum matching in a graph is an easy problem (i.e., it can be solved by efficient algorithms), it is not at all evident that the variant defined in terms of reliability is also easy. In fact, it turns out that it is not: it has recently been proved that, given a network and two integers f and d, the problem consisting of deciding whether there exists a set of f edges (links) whose removal decreases the maximum matching number by at least d units is NP-complete, and so it is very likely that it cannot be solved by efficient algorithms. However, it has also been shown that several special cases of interest are tractable. These results constitute a first step in the study of such problems, closely related to the notion of reliability. There are other interesting examples of such problems (we shall develop them in the remaining of the project), showing that this problematic is really an emerging one. However, the systematic study and classification of these problems have not yet been initiated. Therefore, the purpose of the current project is to start the investigations in this field of research. Since it involves a huge amount of (human and financial) resources, our ambition is only to provide a first approach to this problematic, by considering the main problems related to this topic, determining their complexity and designing efficient (exact or heuristic) algorithms to solve them, and eventually sketching a common framework to solve any problem of this type.