|
COATI is a joint project of I3S-CNRS, University of Nice-Sophia Antipolis and INRIA.
|
|
|
|||
|---|---|---|---|---|
|
COATI is a joint project of I3S-CNRS, University of Nice-Sophia Antipolis and INRIA.
|
![[my photo]](./ronan.jpg)
|
Ronan PARDO SOARES PhD Student COATI, INRIA/I3S-CNRS/UNS Sophia Antipolis, France ParGO Research Group, UFC Fortaleza, Brazil |
The central focus of this thesis is the study of structural properties on graphs and how they can be used to aid in the solution of problems arising in telecommunication. By structural properties, we mainly refer to properties that do not depend on the representation of the graph. Unfortunately, there is no common formal definition of a structural property of a graph. Therefore, to illustrate this notion we give some examples: one simple example structural property is the exclusion of cycles. That is, the family of graphs known as forests. Another important structural property is planarity, which gave rise to the notion of graph with bounded genus. In other words, graph structural properties are the ones that can be described by either excluding a pattern, for example a minor or a subgraph, or by enforcing the graph have some underlying structure, for example be embeddable into a given surface, have some bounded parameter or being connected. There are several problems in graph theory that are NP-hard or PSPACE-complete for arbitrary graphs, but, when restricted to graphs with some structural property, they become easy to solve.
We investigate problems arising in telecommunication networks by focusing on the study of three wide and fundamental subjects in graph theory: graph decompositions, pursuit-evasion games and graph convexity.
We start by studying problem of routing reconfiguration in WDM networks, a problem which can be restated as a pursuit-evasion game known as the Process game. By investigating the Process game we were able to design a graph decomposition, the Process Decomposition, which can be used to solve the original problem of routing reconfiguration.
Since graph decompositions can help in the solution several telecommunication problems including the routing reconfiguration problem, following the study of the Process game, we delve on the computational aspects of constructing some graph decompositions.
We then proceed to focus on another telecommunication problem, the problem of prefetching web-pages, which can also be understood as a pursuit-evasion game, the Surveillance Game.
Since pursuit-evasion games can be used to model a wide variety of telecommunication problems, we attempt to investigate turn-by-turn pursuit-evasion games in general. Albeit these games have different set of rules, they all share some common characteristics. We propose a framework to model all these games by considering them as convex games. This allows us to study these games as linear programs and use techniques such as linear relaxation to solve such problems.
The last part of this thesis is dedicated to graph convexity a topic that can help understanding spread of an infection on a network. Our aim is at answering what graph structural property makes the computation of the hull number of a graph hard.
The Process game is a pursuit-evasion game motivated by the problem of routing reconfiguration in WDM networks. This game is similar to classical graph searching games, such as the Node Search game, but with two major differences, the first one is that the game is played on a directed graph and the second one is that the fugitive loses as soon as it is not able to reach a strongly connected component free of searchers.
One first question we investigate is the role of monotonicity in the Process game. We aim at answering if backtracking helps in the problem of routing reconfiguration in WDM networks. In the routing reconfiguration problem this means that once a connection is re-established in its final routing that connection cannot change its routing. In its original definition, backtracking is not allowed in the problem of routing reconfiguration in WDM networks, consequently the rules for the movements of the searchers do not allow recontamination. We relax this constraint to allow recontamination, then we prove that this does not help the searchers. In other words, we show that the Process game is monotone. The monotonicity of the Process game means that it backtracking does not help reconfigure a routing.
This monotonicity allows us to design a decomposition of the graph, the Process Decomposition, that represents monotone strategies for the Process game. This means that the problem of routing reconfiguration can be restated as the problem of computing a Process Decomposition.
The results presented in this chapter have been presented in LAGOS2013.
We then proceed to investigate the problem of computing graph decompositions. In the literature, there are FPT-algorithms to compute several graph decompositions (such as: the tree decomposition, the path decomposition, branch decomposition, linear decomposition, cut decomposition and carving decomposition). The existent algorithms for all the aforementioned decompositions, usually, are based on dynamic programming of the tree decomposition of the input graph. We aim at answering if all these algorithms are the same. That is, we aim at answering the questions if it is possible to have an unified algorithm to compute all the aforementioned decompositions and if there are other decompositions that could be computed using this dynamic programming approach.
Based on the representation of these decompositions with partitioning functions, we propose an algorithm to compute any of the aforementioned decompositions. This algorithm can also compute the special tree decomposition and the q-branched tree decomposition for which no known algorithms currently exists.
We also investigate other pursuit-evasion games related to problems in telecommunication networks such as the Surveillance Game. This game, motivated by the problem of prefetching web-pages from the web to minimize the waiting time of a web-surfer that browses the web, has two players a surfer (playing the role of the robber) and an observer (playing the role of the cops). The game is played turn by turn, with the observer playing first. In the beginning of the game, one vertex of the graph is marked and occupied by the surfer. The observer plays by marking a given number of vertices of the graph, while the surfer plays by moving along an edge of the graph. The surfer wins if he is able to reach an unmarked vertex, otherwise the marker wins when he finishes to mark all vertices of the graph.
We study two versions of the Surveillance game: the Connected Surveillance game and the Online Surveillance game. These two versions models the aforesaid problem of prefetching more realistically. In the connected version, the observer is obliged to keep the marked area connected during all steps of the game, while in the online version he, initially, can only ``see'' the vertex initially marked and its neighbourhood and discovers other vertices of the graph by marking neighbors of the marked vertices.
We aim at investigating how big can be the gap between the number of marks per turn necessary to guarantee a victory for the observer between these games. A small gap would imply that results for the (original) Surveillance could translate well to the other two games.
We show that, unfortunately, the best online strategy is to mark neighbours of the surfer's position at each step. For the connected variant, we show that the connected surveillance number is at most (n.sn(G))1/2 in any n-node graph G with surveillance number sn(G). On the other hand, we exhibit a family of graphs G with connected surveillance number equal to sn(G)+2. The gap for the connected variant is still huge.
The results presented in this chapter have been presented in SIROCCO2013.
Since, finding the minimum amount of resources to guarantee the victory of the "cops" in pursuit-evasion games is a hard question (NP-hard, PSPACE-complete) in general, we propose a framework to relax the constraint that tokens used by both players must be integral. In other words, we permit both players to move and use parts of a token. To further explain what a part of a token means consider the fractional Cops and Robbers game, for example. In this game, cops and robbers can play in a fractional way, that is, it is possible to have half a cop in a vertex while there is a third of a robber in some other vertex.
Pursuit-evasion games that can be described using this framework includes, but is not limited to, several variants of the Cops and Robbers game, the Angel Problem game, the Eternal Dominating Set game and the Surveillance game. We aim at analysing the behaviour of such games when the integrality of the tokens for each player, or just for the pursuer, is relaxed.
We provide an algorithm to decide whether the pursuer has a winning strategy against the evader for any game that fit in this framework. This is achieved by considering the game as a convex game and applying linear programming techniques.
These fractional games are also shown to give lower bounds to their integral versions. These lower bounds also allows us to develop the first approximability results for the Surveillance Game and the Angel Problem.
The results presented in this chapter have been presented in ALGOTEL2013.
The topic of graph convexity tries to bring general concepts of convexity to graphs. We focus on the Geodetic convexity (the convexity defined by shortest paths), a subject which models the spread of infection in telecommunication networks. It is known that computing the hull number is NP-hard for general graphs, but can be done in polynomial time on cographs, split graphs, unity interval graphs, distance hereditary graphs and chordal graphs. We investigate several other graph classes in an attempt to pinpoint where does the hardness of computing the hull number lies.
We show that computing the hull number of a bipartite graph is NP-hard. We then investigate this question on complement of bipartite graphs. That is, if instead of having two stable sets joined by some edges, we have two cliques joined by some edges. We successfully show that computing he hull number of a complement of bipartite graphs can be done in polynomial time.
We also show that computing the hull number of a graph can be done in polynomial time on the class of (q,q-4)-graphs which is a supper class of cographs. Since cographs are graphs with no induced P4 and (q, q-4)-graphs are graphs with "few" induced P4s, we investigate a class of graphs that allows P4s but forbids P5s. We show that, under an extra assumption that the graph is also free of triangles, it is possible to compute its hull number in polynomial time.
We propose the first FPT-algorithm for computing the hull number of general graphs, where the parameter is either the minimum vertex cover of a graph or its neighbourhood diversity. Moreover, the techniques used to design this FPT-algorithm also allows us to characterize the hull number of the lexicographic products of graphs based on the hull number of its factors.
The results presented in this chapter have been presented in LAGOS2013, in EUROCOMB2011 and were published in TCS.