Chennai Mathematical Institute


11.30 am, Seminar Hall
Finding Transitive Subgraphs and Counting Popular Matchings

Nitesh Jha
Chennai Mathematical Institute.


In this talk we will look at an overview of the thesis that consists of two different problems from an algorithmic perspective: the Transitivity Problem in Directed Graphs, and the Popular Matching Problem.

The Transitive Problem involves obtaining optimal transitive subgraphs of a given directed graph. We present an algorithm that, given a directed graph on $n$ vertices and $m$ arcs outputs a maximal transitive subgraph in time $O(n^2 + nm)$. In the case of Maximum Transitive Subgraph (MTS) problem, we give a 0.25-approximation for the general problem and a 0.874-approximation for the triangle-free case (underlying graph being triangle-free). We also give an upper bound on the size of MTS being $m/4 + cm^{4/5}$ for some $c > 0$. Further, we give exact algorithms for the MTS problem in different settings. We prove that the MTS problem is Fixed-parameter tractable when parameterized by treewidth.

In the later part of the thesis, we study the problem of Popular Matchings. Here our goal is to count the number of popular matchings in a given instance. We give some hardness and approximation results for the same.