PUBLIC VIVAVOCE NOTIFICATION (COMPUTER SCIENCE) 11.30 am, Seminar Hall Finding Transitive Subgraphs and Counting Popular Matchings Nitesh Jha Chennai Mathematical Institute. 120717 Abstract 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.25approximation for the general problem and a 0.874approximation for the trianglefree case (underlying graph being trianglefree). 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 Fixedparameter 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.
