Showing 2025 · cs.DSShow all
2 papers · 2 filters
cs.DS2025
FPT algorithms over linear delta-matroids with applications
Eduard Eiben, Tomohiro Koana, Magnus Wahlström
Matroids, particularly linear ones, have been a powerful tool in parameterized complexity for algorithms and kernelization. They have sped up or replaced dynamic programming. Delta…
cs.DS2025
Polynomial Kernel and Incompressibility for Prison-Free Edge Deletion and Completion
Séhane Bel Houari-Durand, Eduard Eiben, Magnus Wahlström
Given a graph and an integer , the -free Edge Deletion problem asks whether there exists a set of at most edges of whose deletion makes free of induced copies…