•   When: Friday, June 15, 2018 from 01:00 PM to 03:00 PM
•   Speakers: Indranil Banerjee
•   Location: ENGR 4201
•   Export to iCal

This dissertation sets out to explore the complexity of some fundamental combinatorial problems in both deterministic and randomized settings. We divide the work into two parts: 1) Problems on order and 2) Problems on graph reconfiguration. In the former setting, we first study generalizations of the standard sorting problem followed by a more abstract problem known as the set-maxima problem.  Additionally, we look at some special cases of these problems.  In the second part we study some specific versions of the broadly defined graph reconfiguration problem. Using a matching model we give both structural and computational complexity results for routing and sorting on graphs. Some of these results have already been extended by other authors and several interesting problems have been discovered that remains open. We believe these would be of interest to a broader audience in the future.

The first part of the dissertation focuses on a structured cost model. This is motivated by the fact that the uniform cost model does not provide an accurate estimate of the runtime of an algorithm in many real world scenarios. However, an arbitrary cost model may not be that useful. It has been proven that even for very simple problems it is not possible to find a cost-optimal algorithm if the comparison costs are arbitrarily chosen by an adversary. With this in mind we look at a restricted cost model; we assume that comparison costs are either 1 or "infinity". In this setting, given two objects from our universe we can either compare them and determine their order, at a cost of one unit, or the pair is incomparable and cannot be compared directly. In our problem description, along with the set of elements, we are also given an undirected graph. There is an edge between two elements if and only if the pair can be compared. We also look at the case when this graph is a random graph. In both of these settings we have made progress with regard to the problem of sorting when some pairs of elements are incomparable. For example, in the structured cost model we give the first nontrivial deterministic algorithm for the problem, which is also optimal for certain special cases. Another comparison-based problem is the well known set-maxima problem, which is to determine the maximum element of every subset from a collection of subsets of a given set. The general case has remained unsolved for about 40 years. Some special cases have been considered in the past. Following this tradition, we give an optimal deterministic algorithm based on a geometric formulation of this problem.

In the second part of this work, we focus our attention to graph reconfiguration. We propose a unifying model for graph reconfiguration and discuss several known problems as special cases of this model. Notably, we study the permutation routing and the oblivious sorting problem on graphs. For these problems we give several complexity and structural results. These include proving hardness results of routing and some of its variants. We give bounds on various routing and sorting parameters, for different family of graphs. Additionally, we also give explicit sorting networks for trees and the pyramid graph, which are the first of their kind.