Representative set statements for delta-matroids and the Mader delta-matroid
Magnus Wahlström · Society for Industrial and Applied Mathematics eBooks · 2024
The representative sets lemma for linear matroids has many powerful surprising applications in parameterized complexity, including improved FPT dynamic programming algorithms (Fomin et al., JACM 2016) and polynomial kernelization and sparsification results for graph separation problems (Kratsch and Wahlström, JACM 2020). However, its application can be sporadic, as it presupposes the existence of a linear matroid encoding a property relevant to the problem at hand. Correspondingly, although its application led to several new kernelizations (e.g., Almost 2-SAT and restricted variants of MuLTIWAY Cut), there are also several problems left open (e.g., the general case of MuLTIWAY Cut).