Please note: This PhD defence will be given online.
Jan
Gorzny,
PhD
candidate
David
R.
Cheriton
School
of
Computer
Science
Supervisor: Professor Jonathan Buss
An asteroidal triple (AT) is a triple of independent vertices x, y, z such that between every pair of vertices in the triple, there is a path that does not intersect the closed neighbourhood of the third. A graph without an asteroidal triple is said to be AT-free.
An ordering of a graph G is a bijection of V (G) to {1, . . . , |V (G)|}. In this thesis, we consider the complexity of two types of ordering problems. The first type of problem we consider minimize objective functions related to an ordering of the graph. We consider the problems Cutwidth, Imbalance, and Optimal Linear Arrangement. We also consider a problem of another type: S-End-Vertex, where S is one of the following search algorithms: breadth-first search (BFS), lexicographic breadth-first search (LBFS), depth-first search (DFS), and maximal neighbourhood search (MNS). This problem asks if a specified vertex can be the last vertex in an ordering generated by S. We show that, for each type of problem, orderings for one problem may be related to orderings for another problem of that type.
We show that there is always a cutwidth-minimal ordering where equivalence classes of true twins are grouped for any graph, where true twins are vertices with the same closed neighbourhood. This enables a fixed-parameter tractable (FPT) algorithm for Cutwidth on graphs with bounded edge clique cover number and a new parameter, the restricted twin cover number of the graph. The restricted twin cover number of the graph generalizes the vertex cover number of a graph, and is the smallest value k ≥ 0 such that there is a twin cover of the graph T and k −|T| non-trivial components of G−T.
We show there is also always an imbalance-minimal ordering where equivalence classes of true twins are grouped for any graph. We show a polynomial time algorithm for this problem on superfragile graphs and subsets of proper interval graphs, both subsets of AT-free graphs. In the FPT setting, we improve algorithms for Imbalance on graphs with bounded vertex cover number and show that the problem does not have a polynomially sized kernel for graphs with bounded vertex cover number unless NP ⊆ coNP/poly. We provide closed formulas for Imbalance on some small graph classes.
We show that Optimal Linear Arrangement also has a polynomial algorithm for superfragile graphs and an FPT algorithm with respect to the restricted twin cover number.
Finally, we consider S-End-Vertex, for BFS, LBFS, DFS, and MNS. We perform the first systematic study of the problem on bipartite permutation graphs, a subset of AT-free graphs. We show that for BFS and MNS, the problem has a polynomial time solution. We improve previous results for LBFS, obtaining a linear time algorithm. For DFS, we establish a linear time algorithm. All the results follow from the linear structure of bipartite permutation graphs.
To join this PhD defence on Zoom, please go to https://uwaterloo.zoom.us/j/91910576090?pwd=em91RHNqZFJ1UUZVV0xjQU1QcDlEZz09.