58 citations · 151 across the 35 of their papers we have counts for
44 papers
Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances
Joshua Brakensiek, Venkatesan Guruswami, Bart M. P. Jansen +2
We say that an instance of a constraint satisfaction problem (CSP) is non-redundant if the satisfaction of each clause cannot be implied by the satisfaction of the other clauses in…
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…
Kernelization for list -coloring for graphs with small vertex cover
Marta Piecyk, Astrid Pieterse, Paweł Rzążewski +1
For a fixed graph , in the List -Coloring problem, we are given a graph along with list for every , and we have to determine if there ex…
The Richness of CSP Non-redundancy
Joshua Brakensiek, Venkatesan Guruswami, Bart M. P. Jansen +2
In the field of constraint satisfaction problems (CSP), a clause is called redundant if its satisfaction is implied by satisfying all other clauses. An instance of CSP is call…
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…