Abstract
This thesis considers several graph theory problems and parameters, all related to the concept of chordal triangulation. The first of such problems is the wellestablished MINIMUM FILLIN problem solved by finding a minimum triangulation of the input graph, one that minimizes the number of added edges. Since this problem is shown to be NPhard, our study will involve introducing new reduction rules for the MINIMUM FILLIN problem. We will also prove some new properties of elimination orderings, a common tool for constructing triangulations. Later, we will combine and apply the aforementioned results by implementing a minimum fillin program, which was our submission to the PACE challenge 2017 [45]. Next, we focus on the extensivelystudied TREEWIDTH problem, which is solved by finding a triangulation where the size of the largest clique is minimized. Our results in this area include determining the treewidth for several gridlike graph classes, for which the exact value of this parameter was previously unknown.Another closely related class of problems studied in this thesis is the INERT NODE SEARCHING problem. It was previously assumed, due to [56], that the variant of this problem concerned with minimizing the search cost parameter is equivalent to the MINIMUM FILLIN problem. Among our contributions, we noted a mistake in their result and amended it by introducing a new parameter called guard cost that is proved to have the previously mentioned property.
The last part of this thesis is dedicated to whether there exists a triangulation solving both problems MINIMUM FILLIN and TREEWIDTH simultaneously. For this purpose, we introduce a new graph parameter labelled as τ. Given a graph and a minimum triangulation that minimizes the size of the largest clique, τ of the input graph is the difference between the size of this largest clique minus 1 and the treewidth of the original graph. We first prove that τ = 0 for various classes of graphs, thus showing that both MINIMUM FILLIN and TREEWIDTH problems can be solved using the same triangulation. However, we prove that τ > 0 for relatively small instances of rook’s graphs, an already established gridlike graph. As a consequence of our work, we will also determine the previously unknown minimum fillin parameter of the studied graph classes.
Date of Award  Feb 2022 

Original language  English 
Awarding Institution 

Supervisor  Janka Chlebikova (Supervisor), Mohamed BaderElDen (Supervisor) & Alexander Gegov (Supervisor) 