58 citations · 151 across the 35 of their papers we have counts for
29 papers · 1 filter
Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables
Peter Jonsson, Victor Lagerkvist, Jorke M. de Vlas +1
We study a model of constraint satisfaction problems geared towards instances with few variables but with domain of unbounded size (udCSP). Our model is inspired by recent work on…
Faster algorithms on linear delta-matroids
Tomohiro Koana, Magnus Wahlström
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…
Representative set statements for delta-matroids and the Mader delta-matroid
Magnus Wahlström
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 e…
On weighted graph separation problems and flow-augmentation
Eun Jung Kim, Tomáš Masařík, Marcin Pilipczuk +2
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 \te…
Flow-augmentation I: Directed graphs
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk +1
We show a flow-augmentation algorithm in directed graphs: There exists a randomized polynomial-time algorithm that, given a directed graph , two vertices , and an…
Near-linear-time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs
Zhiyang He, Jason Li, Magnus Wahlström
Let be a graph and be (possibly overlapping) sets of terminals, . We are interested in computing a vertex sparsifier for terminal cuts in ,…