Graph partitions with proportional density and colouring constraints

  • Clément Dallard

Student thesis: Doctoral Thesis


Motivated by real life challenges and pure research curiosity, this thesis considers several combinatorial problems related to combinatorial optimisation, computational complexity and graph theory. In each chapter, our goal is to refine our understanding of the complexity of the studied problem. When considering N Phardproblems, we eventually circumvent the expected exponential complexity by providing parameterized and approximation algorithms. We also study the problems on restricted type of instances and propose efficient polynomial-time algorithms.
We study the notions of proportional density and define a proportionally dense
subgraph as a subgraph whose vertices have proportionally as many neighbours
inside the subgraph as in the whole graph. This notion combines local and global properties of the subgraph, an interesting paradigm rarely encountered in graph theory. Two problems related to proportionally dense subgraphs are studied, from the perspectives of structural graph theory, computational complexity and approximation. Then, we focus on a graph partitioning problem on vertex-coloured graphs, and study its complexity on restricted classes of caterpillars with bounded hair-length and planar graphs. Our contributions expose a gap in the complexity of the problem with regard to the hair-length and the maximum degree of the graph. Lastly, we propose a complexity study of a scheduling problem with fixed route and soft time constraints. We show that the problem’s complexity inherently depends on the ride time constraints and give several polynomial-time algorithms for restricted type of instances.
Date of AwardSept 2019
Original languageEnglish
SupervisorJanka Chlebikova (Supervisor), Mohamed Bader-El-Den (Supervisor) & Alexander Gegov (Supervisor)

Cite this