Abstract
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 Award | Sept 2019 |
|---|---|
| Original language | English |
| Awarding Institution |
|
| Supervisor | Janka Chlebikova (Supervisor), Mohamed Bader-El-Den (Supervisor) & Alexander Gegov (Supervisor) |