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 in a graph is a set of three independent vertices such that between any two of them, there is a path that does not contain 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 ordering problems Cutwidth, Imbalance, and Optimal Linear Arrangement, as well as the S-End-Vertex problem, on AT-free graphs and in the parameterized complexity setting.
First, we show that results for Cutwidth can be applied to Imbalance, and that those results in turn can be applied to obtain complexity results for Optimal Linear Arrangement. On some graph classes, there is an ordering which is optimal for all three problems simultaneously. Along the way, we show that there are optimal orderings where each set of true twins in the graph appears consecutively for each of these problems. These results yield fixed-parameter tractable (FPT) algorithms for these problems when the parameter is a variant of the twin-cover or the (edge-)clique-cover number.
We obtain tractable algorithms for Imbalance on various classes of AT-free graphs, which match the complexity of algorithms for Cutwidth on these classes. We show that Imbalance is NP-complete for split graphs, but can be solved on threshold graphs — the AT-free restriction of this class of graphs — in linear time. We obtain tractable results for other subclasses of AT-free graphs: Imbalance can be solved in linear time on proper interval graphs and bipartite permutation graphs, an-d in polynomial time on superfragile graphs. We observe that the best-known FPT algorithm for Cutwidth on graphs with bounded vertex cover can be adapted for Imbalance, and the reduction that shows Cutwidth likely has no polynomial-sized kernel for bounded vertex cover number graphs also applies to Imbalance. These results also follow from the fact that there are Imbalance-optimal orderings where each set of true twins in the graph appears consecutively. We also determine closed formulas for Imbalance on very small graph classes which have closed formulas for Cutwidth.
In turn, the Imbalance results lead to tractable algorithms for Optimal Linear Arrangement. We show that Optimal Linear Arrangement has a linear time algorithm for threshold graphs, and polynomial time algorithms for bipartite permutation graphs and superfragile graphs.
Finally, we consider the question of whether a particular vertex can be visited last a search algorithm $S$: this is the S-End-Vertex problem. We perform the first systematic study of the problem on bipartite permutation graphs. We improve the previous result for Lexicographic Breadth-First Search, and show new positive results for Maximal Neighbourhood Search, Depth-First Search, and Breadth-First Search.
To join this PhD defence on Zoom, please go to https://us02web.zoom.us/j/81596822990?pwd=UjdXa0hHYUhhRkxkNWxteWQwOHp6Zz09.