Loading Events

« All Events

  • This event has passed.

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

April 16 Tuesday @ 4:30 PM - 5:30 PM KST

Room B332, IBS (기초과학연구원)

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.


April 16 Tuesday
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:


Room B332
IBS (기초과학연구원) + Google Map


Sang-il Oum (엄상일)
View Organizer Website
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: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.