121 citations · 128 across the 9 of their papers we have counts for
15 papers
Quasi-polynomial-sized vertex multicut-mimicking networks and kernelization for Vertex Multiway Cut
Eduard Eiben, Roohani Sharma, Magnus Wahlström
We give deterministic polynomial-time constructions of vertex multicut-mimicking networks of quasi-polynomial size. Given a graph G, a terminal set T, and a positive integer c, our…
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 , ,…
Parameterized Complexity of Equality MinCSP
George Osipov, Magnus Wahlström
We study the parameterized complexity of MinCSP for so-called equality languages, i.e., for finite languages over an infinite domain such as , where the relations are d…
Determinantal Sieving
Eduard Eiben, Tomohiro Koana, Magnus Wahlström
We introduce determinantal sieving, a new, remarkably powerful tool in the toolbox of algebraic FPT algorithms. Given a polynomial on a set of variables $X=\{x_1,\ldots,x_n\…
On the parameterized complexity of symmetric directed multicut
Eduard Eiben, Clément Rambaud, Magnus Wahlström
We study the problem Symmetric Directed Multicut from a parameterized complexity perspective. In this problem, the input is a digraph , a set of cut requests $C=\{(s_1,t_1),\ldo…
Almost Consistent Systems of Linear Equations
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak +2
Checking whether a system of linear equations is consistent is a basic computational problem with ubiquitous applications. When dealing with inconsistent systems, one may seek an a…
Preference Swaps for the Stable Matching Problem
Eduard Eiben, Gregory Gutin, Philip R. Neary +3
An instance of the Stable Matching Problem (SMP) is given by a bipartite graph with a preference list of neighbors for every vertex. A swap in is the exchange of two consec…
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…
LP-branching algorithms based on biased graphs
Euiwoong Lee, Magnus Wahlström
We give a combinatorial condition for the existence of efficient, LP-based FPT algorithms for a broad class of graph-theoretical optimisation problems. Our condition is based on th…
On Problems as Hard as CNFSAT
Marek Cygan, Holger Dell, Daniel Lokshtanov +6
The field of exact exponential time algorithms for NP-hard problems has thrived over the last decade. While exhaustive search remains asymptotically the fastest known algorithm for…
Representative sets and irrelevant vertices: New tools for kernelization
Stefan Kratsch, Magnus Wahlström
The existence of a polynomial kernel for Odd Cycle Transversal was a notorious open problem in parameterized complexity. Recently, this was settled by the present authors (Kratsch…