8 citations · 12 across the 5 of their papers we have counts for
Showing 2013Show all
3 papers · 1 filter
cs.CC2013
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…
cs.DS2013★ 8 cited
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…
cs.CC2013★ 3 cited
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…