Schedule for 28th November 2019

9:30-10:15: Graphs with Possible Loops -- Pavol Hell

Abstract: I will discuss a few examples of concepts that have interesting extensions if loops are allowed (but not required). I will include interval graphs, strongly chordal graphs, and other concepts, and illustrate possible algorithmic advantages of such extensions.

10:15-11:00: Planar Maximum Matchings: Towards a parallel algorithm -- Samir Datta

Abstract: Perfect matchings in planar graphs have been extensively studied and understood in the context of parallel complexity. In particular, perfect and more recently, maximum matchings in planar and other restricted graph classes have been intensively studied.

In this talk, we summarise the method of non-vanishing circulations applicable to perfect matchings in restricted graph classes. We show how this method naturally extends to maximum matchings in these classes.

Then we show an NC-reduction from search to decision, in the case of planar maximum matchings. We also show an NC-reduction for counting planar maximum matchings to counting bipartite planar matchings in the presence of an oracle for deciding planar maximum matchings.

Our bounds and reductions combine techniques like the Gallai-Edmonds decomposition, deterministic isolation, and the recent breakthroughs in the parallel search for planar perfect matchings.

The talk is based on Datta-Kulkarni-Kumar-Mukherjee (ISAAC'18).

.

11:00-1130: COFFEE BREAK

11:30-12:15: Classified Matching -- Prajakta Nimbhorkar

Abstract: While assigning resident doctors to hospitals, one encounters a many-to-one matching problem. A resident is to be matched to one hospital, however, each hospital can employ several residents up to a maximum limit. Residents have preferences over hospitals. The goal is to compute an assignment of residents to hospitals such that maximum number of residents get their first choice, subject to that, maximum number of residents get their second choice and so on. Such a matching is said to be rank-maximal.

We generalize this to the case where a hospital can specify a classification over the residents acceptable to it. Classifications arise naturally in this setting, since residents have different specializations and each hospital needs residents from multiple specializations. A classification for a hospital h is a set of subsets of the neighborhood of h, and each subset has its own upper quota.

We show that the problem has a polynomial-time algorithm when all the classifications are laminar, and is NP-complete otherwise.

12:15-13:00: Stability, Popularity and Lower Quotas -- Meghana Nasre

Abstract: We consider the problem of assigning a set of men to a set of women where each participant ranks members of the opposite side in an order of preference. This is called the stable marriage problem in literature. It is well known that every instance of the stable marriage problem admits a "stable matching" which can be computed efficiently by the Gale and Shapley algorithm. In this talk we consider three variants of the stable marriage problem where

(a) Preference lists can contain ties, (b) Preference lists can be incomplete, (c) Vertices can have lower quotas

For each of these variants a different notion of optimality is applicable; yet we show that, a simple extension of the Gale and Shapley algorithm computes an optimal matching in each of them. The talk is based on three papers -- Z. Kiraly (Algorithmica 2011), T. Kavitha (SICOMP 2014) and Nasre and Nimbhorkar (FSTTCS 2017).

13:00-1415: LUNCH BREAK

14:15-15:00: Structured Tree Decompositions and Applications -- Fahad Panolan

Abstract: The treewidth of a graph measures how close the graph to a tree like structure and it is frequently used in the design of parameterized algorithms. When the treewidth of the input graph is large, efficient algorithms can be designed using grid-minor theorems, bidimensionality and decomposition theorems on various graph classes like planar graphs. The structure of a bag in a tree decomposition can also be exploited to design efficient algorithms. For example, a chordal graph has tree decomposition where every bag is a clique. This leads to polynomial time algorithms for problems like Vertex Cover and Feedback Vertex Set on chordal graphs. In this talk we see how the structure of the graph induced on each bag can be exploited in the design of parameterized algorithms.

15:00-15:30: COFFEE BREAK

16:15-17:00: Parameterized Algorithms and Quadratic Kernels for Rainbow Matching -- Sanjukta Roy

Abstract: We will study the NP-complete colorful variant of the classic matching problem, namely, the Rainbow Matching problem. Given an edge-colored graph G and a positive integer k, the goal is to decide whether there exists a matching of size at least k such that the edges in the matching have distinct colors. We study this problem from the view point of Parameterized Complexity and give efficient FPT algorithms as well as a quadratic kernel.

Schedule for 29th November 2019

09:30-10:15: Oriented and Directed Variants of Gyarfas-Sumner conjecture -- Sunil Chandran

Abstract: Gyarfas-Sumner conjecture states the following: Let a, b be two positive integers. Then there exists a function f(), such that if G is a graph of clique number at most a and chromatic number at least f(a,b), then G contains all trees on s vertices as induced subgraphs. This conjecture is still open, though for several special cases it is known to be true. We study some oriented variants of this conjecture: Does there exist a function g(), such that if the chromatic number of an oriented graph G (satisfying certain properties) is at least g(s) then G contains all oriented trees as its induced subgraphs. We also consider a rainbow (colorful) variant of this conjecture.

10:15-11:00: The Lexicographic Method for the Threshold Dimension Problem -- Mathew Francis

Abstract: The lexicographic method is a technique that was introduced by Hell and Huang in 1995 as a way to simplify the problems of recognizing and obtaining representations of comparability graphs, proper circular-arc graphs and proper interval graphs. This method gives rise to conceptually simple recognition algorithms and leads to much simpler proofs for some characterization theorems for these classes. The threshold dimension of a graph is the minimum number of threshold graphs using which the edges of the graph can be covered. Chvatal and Hammer conjectured in 1977 that given a graph G, a suitably constructed auxiliary graph G' has chromatic number equal to the threshold dimension of G. Although this conjecture was shown to be false in the general case by Cozzens and Leibowitz, it was shown to be true for graphs having threshold dimension at most 2 by Raschle and Simon in 1995. We will discuss how the lexicographic method can be used to obtain a completely new and much simpler proof for this result. This method also gives rise to a simple new algorithm for recognizing graphs of threshold dimension at most 2. Although this algorithm is not the fastest known, it is a certifying algorithm that matches the time complexity of the fastest known certifying algorithm for this problem.

11:00-11:30: COFEE BREAK

11:30-12:15: Coloring of Some Special Classes of Graphs -- T. Karthick

Abstract: The chromatic number of a graph G is the minimum number of colors required to color the vertices of G so that no two adjacent vertices receive the same color. In this talk, we show bounds for the chromatic number of some special classes of graphs which are defined by forbidden induced subgraphs via structure theorems

12:15-13:00: Parameterized Complexity of (n − k) List Coloring -- Ashwin Jacob

Abstract: The classical graph coloring problem is given an undirected graph and the goal is to color the vertices of the graph with minimum number of colors so that end points of each edge gets different colors. In list-coloring, each vertex is given a list of allowed colors with which it can be colored. We look at the list-coloring problem from the perspective of parameterized complexity. It is clear that the the number of colors k as a parameter is not interesting for graph coloring, as the problem is NP-hard even for k = 3. An interesting parameterization for graph coloring that has been studied is whether the graph can be colored with n − k colors, where k is the parameter and n is the number of vertices. This is known to be fixed parameter tractable using the notion of crown reduction. We generalize thisfor list-coloring as well. We will look at a number of algorithms which given a graph with each vertex having a list of size n − k, determines in f(k)n^{O(1)} time whether there is a coloring that respects the lists, for some function f of k.

.

13:00-14:15: LUNCH BREAK

14:15-15:00: Parameterization Above a Multiplicative Guarantee -- Saket Saurabh

Abstract: In this talk we will speak about new paradigm in above guaranteed parameterizations with some concrete examples.

15:00:15:30: COFFEE BREAK

15:30-16:30: A Graph Theorist’s Perspective on the Quest for Dichotomy -- Pavol Hell

Abstract: The celebrated Feder-Vardi Dichotomy Conjecture for Constraint Satisfaction has recently been established by Bulatov and by Zhuk. Because of the profound impact the conjecture had on theoretical computer science, Feder and Vardi were jointly awarded the Alonzo Church Award for 2019. The solution involved a beautiful blend of graph theory, logic, and universal algebra, developed over a period of 25 years; and these developments, in turn, have impacted all these fields. I will present a personal account of how one graph-theorist perceived the events and developments leading up to the formulation, and the solution, of the conjecture.

(This is a seminar for general audience and will be held in Ramanujan Auditorium.)