PhD defense of Guillaume Ducoffe

• Victor Chepoi (Referee), LIF, Marseille, France
• David Coudert (Supervisor), Université Côte d’Azur, Inria, CNRS, I3S, France
• Michele Flammini, University of L’Aquila, Italie
• Cyril Gavoille, LaBRI – Université de Bordeaux, France
• Igor Litovsky, I3S, Univ. Nice Sophia Antipolis, France
• Nicolas Nisse, Université Côte d’Azur, Inria, CNRS, I3S, France
• Robert E. Tarjan, Princeton University and Intertrust Technologies, USA
• Laurent Viennot (Referee), Inria / IRIF, France

Abstract: Large scale communication networks are everywhere, ranging from data centers with millions of servers to social networks with billions of users. This thesis is devoted to the fine-grained complexity analysis of combinatorial problems on these networks.

In the first part, we focus on the embeddability of communication networks to tree topologies. This property has been shown to be crucial in the understanding of some aspects of network traffic (such as congestion). More precisely, we study the computational complexity of Gromov hyperbolicity and of tree decomposition parameters in graphs – including treelength and treebreadth. On the way, we give new bounds on these parameters in several graph classes of interest, some of them being used in the design of data center interconnection networks. The main result in this part is a relationship between treelength and treewidth: another well-studied graph parameter, that gives a unifying view of treelikeness in graphs and has algorithmic applications. This part borrows from graph theory and recent techniques in complexity theory.

The second part of the thesis is on the modeling of two privacy concerns with social networking services. We aim at analyzing information flows in these networks, represented as dynamical processes on graphs. First, a coloring game on graphs is studied as a solution concept for the dynamic of communities. We give a fine-grained complexity analysis for computing Nash and strong Nash equilibria in this game, thereby answering open questions from the literature. On the way, we propose new directions in algorithmic game theory and parallel complexity, using coloring games as a case example. Finally, we introduce a new learning problem that is motivated by the need for users to uncover any misuse of their personal data online. We give positive and negative results on the tractability of this problem.

All the publications at the core of this thesis are available online here

Keywords: Graph theory, Hyperbolicity, tree-decomposition, complexity, privacy.