6 papers
Optimal FPT-Approximability for Modular Linear Equations
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak +2
We show optimal FPT-approximability results for solving almost satisfiable systems of modular linear equations, completing the picture of the parameterized complexity and FPT-appro…
Parameterized Approximability for Modular Linear Equations
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak +2
We consider the Min--Lin problem: given a system of length- linear equations modulo , find of minimum cardinality such that is satisfiable…
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…
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…
Parameterized Complexity of MinCSP over the Point Algebra
George Osipov, Marcin Pilipczuk, Magnus Wahlström
The input in the Minimum-Cost Constraint Satisfaction Problem (MinCSP) over the Point Algebra contains a set of variables, a collection of constraints of the form , ,…
Many visits TSP revisited
Łukasz Kowalik, Shaohua Li, Wojciech Nadara +2
We study the Many Visits TSP problem, where given a number for each of cities and pairwise (possibly asymmetric) integer distances, one has to find an optimal tour that…