Algorithms for Weighted Independent Transversals and Strong Colouring

Aug 03, 2021 09:00 AM Singapore (Registration will open at 08:50 AM.)

Join Zoom Meeting:
https://sutd-edu.zoom.us/j/95198628401?pwd=cXdMTzRoc3FZa2ozcDAxS2xuWDJBUT09

Meeting ID: 951 9862 8401
Passcode: !M3eYjSy

Abstract

An independent transversal (IT) in a graph with a given vertex partition is an independent set consisting of one vertex in each partition class. Several sufficient conditions are known for the existence of an IT in a given graph and vertex partition, which have been used over the years to solve many combinatorial problems. Some of these IT existence theorems have algorithmic proofs, but there remains a gap between the best existential bounds and the bounds obtainable by efficient algorithms.

Recently, Graf and Haxell (2018) described  a new (deterministic) algorithm that asymptotically closes this gap, but there are limitations on its applicability. In this paper we develop a randomized  algorithm that is much more widely applicable, and demonstrate its use by giving efficient algorithms for two problems concerning the strong chromatic number of graphs.

The paper can be found at: https://arxiv.org/abs/1907.00033

About the Speaker

David Harris is an affiliate professor in the Computer Science department at the University of Maryland. He received a PhD from the University of Maryland in 2015 in Applied Mathematics, advised by Dr. Aravind Srinivasan. His research focuses on randomized algorithms and their role in combinatorics and theoretical computer science.

For more information about the ESD Seminar, please email esd_invite@sutd.edu.sg