8 citations · 12 across the 5 of their papers we have counts for
7 papers
Parameterized Intractability of Even Set and Shortest Vector Problem
Arnab Bhattacharyya, Édouard Bonnet, László Egri +5
The -Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over , which can be stated as follows: given a generator matrix $\m…
Fixed-parameter Approximability of Boolean MinCSPs
Édouard Bonnet, László Egri, Bingkai Lin +1
The minimum unsatisfiability version of a constraint satisfaction problem (MinCSP) asks for an assignment where the number of unsatisfied constraints is minimum possible, or equiva…
Space complexity of list H-coloring revisited: the case of oriented trees
Laszlo Egri
Digraphs H for which the list homomorphism problem with template H (LHOM(H)) is in logspace (L) was characterized by Egri et al. (SODA 2014): LHOM(H) is in L if and only if H does…
On Constraint Satisfaction Problems below P
Laszlo Egri
Symmetric Datalog, a fragment of the logic programming language Datalog, is conjectured to capture all constraint satisfaction problems (CSP) in L. Therefore developing tools that…
List H-Coloring a Graph by Removing Few Vertices
Rajesh Chitnis, Laszlo Egri, Daniel Marx
In the deletion version of the list homomorphism problem, we are given graphs G and H, a list L(v) that is a subset of V(H) for each vertex v of G, and an integer k. The task is to…
Space complexity of list H-colouring: a dichotomy
Laszlo Egri, Pavol Hell, Benoit Larose +1
The Dichotomy Conjecture for constraint satisfaction problems (CSPs) states that every CSP is in P or is NP-complete (Feder-Vardi, 1993). It has been verified for conservative prob…
The complexity of the list homomorphism problem for graphs
Laszlo Egri, Andrei Krokhin, Benoit Larose +1
We completely classify the computational complexity of the list H-colouring problem for graphs (with possible loops) in combinatorial and algebraic terms: for every graph H the pro…