Zobrazeno 1 - 10
of 197
pro vyhledávání: '"WAHLSTRÖM, MAGNUS"'
We consider the MIN-r-LIN(R) problem: given a system S of length-r linear equations over a ring R, find a subset of equations Z of minimum cardinality such that S-Z is satisfiable. The problem is NP-hard and UGC-hard to approximate within any constan
Externí odkaz:
http://arxiv.org/abs/2410.09932
Autor:
Koana, Tomohiro, Wahlström, Magnus
We show new algorithms and constructions over linear delta-matroids. We observe an alternative representation for linear delta-matroids, as a contraction representation over a skew-symmetric matrix. This is equivalent to the more standard "twist repr
Externí odkaz:
http://arxiv.org/abs/2402.11596
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 $x < y$, $x = y$, $x \leq y$ and $x \neq y$, and a budget $k$. The goal is to check whe
Externí odkaz:
http://arxiv.org/abs/2310.05839
Autor:
Wahlström, Magnus
We present representative sets-style statements for linear delta-matroids, which are set systems that generalize matroids, with important connections to matching theory and graph embeddings. Furthermore, our proof uses a new approach of sieving polyn
Externí odkaz:
http://arxiv.org/abs/2306.03605
Autor:
Osipov, George, Wahlström, Magnus
We study the parameterized complexity of MinCSP for so-called equality languages, i.e., for finite languages over an infinite domain such as $\mathbb{N}$, where the relations are defined via first-order formulas whose only predicate is $=$. This is a
Externí odkaz:
http://arxiv.org/abs/2305.11131
We introduce determinantal sieving, a new, remarkably powerful tool in the toolbox of algebraic FPT algorithms. Given a polynomial $P(X)$ on a set of variables $X=\{x_1,\ldots,x_n\}$ and a linear matroid $M=(X,\mathcal{I})$ of rank $k$, both over a f
Externí odkaz:
http://arxiv.org/abs/2304.02091
Publikováno v:
SIAM Journal on Discrete Mathematics 38(1), 170-189, 2024
One of the first application of the recently introduced technique of \emph{flow-augmentation} [Kim et al., STOC 2022] is a fixed-parameter algorithm for the weighted version of \textsc{Directed Feedback Vertex Set}, a landmark problem in parameterize
Externí odkaz:
http://arxiv.org/abs/2208.14841
We study the problem Symmetric Directed Multicut from a parameterized complexity perspective. In this problem, the input is a digraph $D$, a set of cut requests $C=\{(s_1,t_1),\ldots,(s_\ell,t_\ell)\}$ and an integer $k$, and the task is to find a se
Externí odkaz:
http://arxiv.org/abs/2208.09017
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 assignment that minimizes the number of unsatisfied equations. This pro
Externí odkaz:
http://arxiv.org/abs/2208.02732
We study the parameterized problem of satisfying ``almost all'' constraints of a given formula $F$ over a fixed, finite Boolean constraint language $\Gamma$, with or without weights. More precisely, for each finite Boolean constraint language $\Gamma
Externí odkaz:
http://arxiv.org/abs/2207.07422