Magnus Wahlström, Algorithmic aspects of linear delta-matroids

Delta-matroids are a generalization of matroids with connections to many parts of graph theory and combinatorics (such as matching theory and the structure of topological graph embeddings). Formally, a delta-matroid is a pair $D=(V,\mathcal F)$ where $\mathcal F$ is a collection of subsets of V known as “feasible sets.” (They can be thought of as generalizing the set of bases of a matroid, while relaxing the condition that all bases must have the same cardinality.)

Like with matroids, an important class of delta-matroids are linear delta-matroids, where the feasible sets are represented via a skew-symmetric matrix. Prominent examples of linear delta-matroids include linear matroids and matching delta-matroids (where the latter are represented via the famous Tutte matrix).

However, the study of algorithms over delta-matroids seems to have been much less developed than over matroids.

In this talk, we review recent results on representations of and algorithms over linear delta-matroids. We first focus on classical polynomial-time aspects. We present a new (equivalent) representation of linear delta-matroids that is more suitable for algorithmic purposes, and we show that so-called delta-sums and unions of linear delta-matroids are linear. As a result, we get faster (randomized) algorithms for Linear Delta-matroid Parity and Linear Delta-matroid Intersection, improving results from Geelen et al. (2004).

We then move on to parameterized complexity aspects of linear delta-matroids. We find that many results regarding linear matroids which have had applications in FPT algorithms and kernelization directly generalize to linear delta-matroids of bounded rank. On the other hand, unlike with matroids, there is a significant difference between the “rank” and “cardinality” parameters – the structure of bounded-cardinality feasible sets in a delta-matroid of unbounded rank is significantly harder to deal with than feasible sets in a bounded-rank delta-matroid.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail:, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.