Department of
Applied
Mathematics

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.