Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 03.11.2016 at 12:20 in S6, there is the following noon lecture:

Beyond perfect matchings: Solving edge-CSP for even delta-matroids

Alexandr Kazda

Abstract

(joint work with Vladimir Kolmogorov and Michal Rolínek)

An instance of edge CSP consists of a set of variables and a set of constraints. Each variable appears in exactly two constraints (so we can draw the instance as a graph where constraints are vertices and variables are edges). The problem is to decide if there exists an assignment of values to variables so that all constraints are satisfied.

We show how to efficiently solve Boolean edge CSPs (ie. edge CSPs where each variable can be either 0 or 1) where constraints are even delta-matroid relations. This kind of edge CSP generalizes the problem of deciding if a given graph has a perfect matching. This is not a coincidence: the algorithm we designed is a generalization of Edmonds' blossom algorithm.

As a consequence of our work, we settle the complexity classification of planar Boolean CSPs started by Z. Dvořák and M. Kupec.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010