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 well-established 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 NP-hard, our study will involve introducing new reduction rules for the MINIMUM FILL-IN 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 fill-in program, which was our submission to the PACE challenge 2017 [45]. Next, we focus on the extensively-studied 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 grid-like 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 FILL-IN 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 FILL-IN 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 FILL-IN 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 grid-like graph. As a consequence of our work, we will also determine the previously unknown minimum fill-in parameter of the studied graph classes.
| Date of Award | Feb 2022 |
|---|---|
| Original language | English |
| Awarding Institution |
|
| Supervisor | Janka Chlebikova (Supervisor), Mohamed Bader-El-Den (Supervisor) & Alexander Gegov (Supervisor) |