2026-08-25T17:34:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27225 2026-08-25T13:18:18Z ddc:004 open_access

FPT Algorithms over Linear Delta-Matroids with Applications Eiben, Eduard Koana, Tomohiro Wahlström, Magnus Delta-matroids parameterized algorithms triangle packing Matroids, particularly linear matroids, have been a powerful tool for applications in parameterized complexity, both for algorithms and kernelization. In particular, they have been instrumental in speeding up or replacing dynamic programming. Delta-matroids are a generalization of matroids that further encapsulate structures such as non-maximum matchings in general graphs and various path-packing and topological structures. There is also a notion of linear delta-matroids (represented by skew-symmetric matrices) which carries significant expressive power and enables powerful algorithms. We investigate parameterized complexity aspects of problems defined over linear delta-matroids, or with delta-matroid constraints. Our initial analysis of basic intersection and packing problems reveals a different complexity landscape compared to the more familiar matroid case. In particular, there is a stark contrast in complexity between the cardinality parameter k and the rank parameter r. For example, finding an intersection of size k of three linear delta-matroids is W[1]-hard when parameterized by k, while far more general problems (such as finding a set packing of size k that is feasible in a given linear delta-matroid) are FPT when parameterized by the rank r of the delta-matroid. In fact, we extend the recent determinantal sieving procedure of Eiben, Koana, and Wahlström (TheoretiCS 2025) into a process that sieves a given polynomial for a monomial whose support is feasible in a given linear delta-matroid, parameterized by r. This is a direct generalization of determinantal sieving. Second, we investigate a curious class of problems that turns out to be FPT parameterized by k, even on delta-matroids of unbounded rank. We begin with Delta-matroid Triangle Cover - find a feasible set of size k that can be covered by a vertex-disjoint packing of triangles (i.e., sets of size 3) out of a given triangle collection. For example, this allows us to find, in a graph, a packing of K₃’s and K₂’s with the maximum possible number of edges, parameterized above the matching number of the graph (note that this problem is NP-hard, unlike the problem of finding such a packing covering a maximum number of vertices, which is tractable). As applications, we resolve the FPT status of Cluster Subgraph and Strong Triadic Closure parameterized above the matching number. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eduard Eiben and Tomohiro Koana and Magnus Wahlström 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.89 urn:nbn:de:0030-drops-272251 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.89 eng https://creativecommons.org/licenses/by/4.0/legalcode